\documentclass[a4paper,10pt,draft]{article}

\newenvironment{mylisting}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\scriptsize\bfseries}
{\end{list}}

\newenvironment{mytinylisting}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\tiny\bfseries}
{\end{list}}

% Paquete para urls
\usepackage{url}
\usepackage{cite}

% Links en indice
\usepackage{hyperref}
\hypersetup{linktocpage}

% Paquetes para el idioma, las tildes, etc.
\usepackage[activeacute,spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{fontenc}
\usepackage{textcomp}

%\usepackage{graphicx}
\usepackage[pdftex]{graphicx}
\DeclareGraphicsExtensions{.bmp, .png, .pdf, .jpg, .jpeg}
\usepackage{subfig}

\renewcommand{\topfraction}{0.85}
\renewcommand{\textfraction}{0.1}
\renewcommand{\floatpagefraction}{0.75}
%\bibliographystyle{plain}
%\bibliography{/home/ramiro/Facu/Swarm.Intelligence/ProyectoTesis/swarm/thesis-swarm/biblio.bib}

%opening
\title{\begin{center}
{\large \textsc{Facultad de Matemática, Astronomía y Física}}\\[0.2cm]
{\textsc{Universidad Nacional de Córdoba}}\\[0.4cm]
\includegraphics[width=0.18\textwidth]{escudo-unc} \\ [1cm]
\begin{flushright} \Large
{
\textbf{Comportamiento Grupal e Información Sensorial}
}
\end{flushright}
\end{center}}


\author{\vspace{6.0cm}\\
\textbf{Directores }\\
		MSc. Carbajal Juan Pablo - \texttt{carbajal@ifi.uzh.ch}\\
		Dr. Blanco Javier - \texttt{blanco@mate.uncor.edu.ar}\\
\\\textbf{Alumno} \\
		Castro, Ramiro David - \texttt{castro.ramiro@gmail.com}}

\begin{document}

\maketitle

\clearpage
\thispagestyle{empty}
\mbox{}
\clearpage

\newpage

\tableofcontents

\clearpage
\thispagestyle{empty}
\mbox{}
\clearpage

\newpage
\section{Agradecimientos}

Primero que nada a mis padres, si no fuera por su apoyo desde pequeño no estaría acá. Gracias por todo lo que me dieron. Gracias por entenderme siempre, por compartir su experiencia de vida, gracias por sus consejos y por a la vez dejarme elegir y equivocarme si era necesario. Los voy a admirar toda mi vida por sus logros. Nada hubiera sido posible si ellos no hubiesen enriquecido mi crecimiento y no hubiesen confiado en mi. A mis hermanos, Sofía y Gonzalo, que pasé casi toda mi vida compartiendo espacios con ellos y supieron ayudarme y entenderme siempre.

A mis amigos de la facultad. Luis Barrueco, que me acompaño en momentos de estudio y grupos. Luis Ferrer, que siempre estuvo dispuesto a prestar tiempo de su vida en explicar cuestiones formales y demostraciones que se escapaban. A Mati Bellone, ahora felizmente casado, con quien pasamos muchas de las primeras horas de la carrera juntos y supo mostrarme lo que es la eficiencia del trabajo. A Pablo Dal Lago y Lucas Rearte que siempre fueron fuente de inspiración, aportando buenas ideas siempre y mostrando que no todo es tan complejo como parece y todo es posible.

A los amigos de la vida, de Viedma del gimnasio, de Muay Thai, imposible contarlos a todos. Todas buenas personas que siempre creyeron en mi, que siempre estuvieron ahí para ayudarme a hacer más ameno los momentos de esta etapa. Me ayudaron siempre a despejar mi cabeza cuando lo necesitaba. Me ayudaron a tener energías, a seguir, a levantar la guardia aunque estemos cansados, a respetar a la gente. Muchas gracias a todos ellos, me hicieron pasar momentos geniales y ayudaron a balancear lo profesional con lo personal.

Muchísimas gracias a Juanpi, que aunque la distancia hace imposible que compartamos momentos juntos, estuvo a mi lado siempre. Un gran mentor, un gran inspirador, una exelente persona, muy inteligente y siempre predispuesto. Siempre con energía, sabiendo guiar el camino. Infinitas gracias a él. Nunca me olvidaré todo el tiempo y ganas que me dedicó sin siquiera conocerme en persona.

A Javier Blanco, una de las primeras caras que vi cuando entré en Fa.M.A.F, que me mostró cosas fascinantes de manera sencilla, que me empezó a enseñar a pensar, que se mostró siempre como una persona ante todo, compartiendo sus conocimientos con los recién ingresados. Persona que ayuda siempre en la tarea tan díficil que es abrir las mentes y encantar a los futuros profesionales.

En el medio hay montones más de personas que estuvieron conmigo una y más veces, es imposible nombrarlos a todos. Pero el hecho de que no estén nombrados en estas palabras es meramente anecdótico ya que no los hace menos importantes porque siempre les voy a estar agradecido. Miles de gracias a los que creyeron y ayudaron, y a los que no también, porque de todos ustedes aprendí algo. 

Intentaré devolver todo lo que me dieron dando lo mejor de mi tanto en lo profesional como en lo personal.

Infinitas gracias a todos! 


\newpage
%
%Computers are incredibly fast, accurate, and stupid; humans
%are incredibly slow, inaccurate, and brilliant; together they
%are powerful beyond imagination - Albert Eintein
%
%
\begin{abstract}
En esta tesis se estudiaron sistemas multi-agente, descentralizados y auto-organizados. Estos sistemas se basan en agentes de poca complejidad que se relacionan entre si y con el medio, donde emerge una complejidad grupal que supera a la individual. Esta complejidad emergente se llama \textit{Inteligencia de ganado (\textbf{\textit{Swarm Intelligence}})} y es ampliamente utilizado en áreas relacionadas a Inteligencia Artificial. Consta de una robustez que es inherente al sistema, ya que su \textit{inteligencia} no está asociada a ningún agente en especial y es una herramienta útil para solucionar problemas de forma descentralizada. 
\end{abstract}

\clearpage
\thispagestyle{empty}
\mbox{}
\clearpage

\newpage
\section{• Motivación}
Todos hemos visto alguna vez bandadas de págaros volando, o cardúmenes de peces, o colonias de hormigas. Y vale la pena preguntarse: ¿Quién controla el grupo?, ¿Quién guía?, ¿Quién arma las \textit{coreografías} que vemos?, ¿Quién tiene la información que el grupo maneja?, ¿Qué tan inteligente tiene que ser cada individuo para poder organizarse junto al resto?, ¿Hay una mente maestra atrás de todo eso?

Estas son preguntas que han intrigado a los científicos por mucho tiempo. Después de todo, sabemos que estos grupos constan de agentes que podemos considerar de una inteligencia limitada. Segundo, estos grupos son sistemas descentralizados, i.e, no hay alguien que concentre toda la información u organice las formas que vemos o decida donde ir. Esto imposibilita la distinción de un agente en particular como líder del grupo, ya que los agentes son iguales unos de otros, nadie se distingue del resto.

Y si es que hay alguien que lidera el grupo, ¿qué pasa si lo quitamos del grupo? ¿se desarmaría, dejarían de organizar formas como antes? Probablemente la respuesta es no, porque de surgir líderes en estos grupos estos son temporales. Es decir, la descentralización del sistema permite que no sea necesario que nadie concentre toda la información o tenga que saber lo que sucede en todo el sistema.

Esta es una de las principales características de la \textit{Inteligencia de Ganado}. La toma de desiciones en un grupo de individuos puede ser muy compleja y depende en buena parte de la interacción entre los agentes. Sin embargo no todos los agentes tienen información buena o confiable, muchas veces \textit{son pocos los agentes que saben donde se encuentra la comida, cual es una buena ruta de migración o la existencia de peligro.} Algunas especies de la naturaleza han evolucionado de forma que el intercambio de información sea mejor, ya sea liberando hormonas que pueden ser reconocidad por otros individuos, emitiendo ruidos característicos o realizando determinados movimientos.

Pero también emergen patrones y organizaciones en grupos donde no se usan señales para comunicar ni se sabe quién tiene la informacion o siquiera si esa información existe y es confiable . De hecho, se ha demostrado que a mayor cantidad de agentes, menor es la información que cada individua debe tener \cite{nature}.

También es altamente estudiada y aplicada la \textit{inteligencia de ganado} por plantear un sistema de cooperación, más conocido como \textit{Control Cooperativo(Cooperative Control)}. Esta característica en un sistema multi-agente nos dice que los agentes cooperan entre si, tomando pequeñas decisiones, cada uno en base a sus valores y en base a la información de su entorno local; sin necesidad de conocer el estado global del sistema.

Cuando tenemos un sistema multi-agente de control cooperativo podemos pensar en beneficios como adaptación en tiempo real o sobreponerse a problemas nuevos no previstos como fallas en los agentes o problemas externos. Estos beneficios se obtienen estudiando la auto-organización de los sistemas y/o la predicción de comportamientos del sistema en si. Más sobre control cooperativo podemos encontrar en \textit{Cooperative Control of Distributed Multi-Agent Systems}\cite{cooperativ-control}.

Todo este intercambio de información, emergencia de patrones y control cooperativo está directamente relacionado con la \textbf{evolución}. Podemos pensar que un individuo de la naturaleza tiene por un lado la información proveniente de sus genes, que definen ciertas reglas básicas que van a regir su vida, y por otro lado tiene la información externa, proveniente del sistema, todo lo que puede sensar. En base a esto debe tomar las desiciones que dirán si sobrevive y evoluciona o no. La \textit{inteligencia artificial} intenta llegar a esto, a la evolución, ya sea de robots o programas. 

Esto es lo que nos interesa estudiar, las formas de interacción entre agentes, poder predecir determinados patrones, la estabilidad o inestabilidad de un sistema, los sensores de los agentes, las reglas que pueden regir a un agente.

\newpage

\section{• Introducción}
El presente trabajo busca estudiar e intentar entender los grupos de sistemas multi agentes, en particular la organización de éstos en base a su interacción y también estudiar distintos tipos de interacción.

Para poder realizar los estudios deseasdos se comenzó identificando dos tipos de modelos distintos basados en la interacción entre los agentes. Por un lado los agentes pueden relacionarse entre sí en base a \textbf{reglas} del tipo \textit{"si $<$condición$>$ entonces $<$acción$>$"}, lo que caracteriza un \textit{\textbf{modelo discreto}} del sistema. Aquí, cada agente deberá analizar las condiciones de las reglas a aplicar y éstas dirán de que forma el agente se tiene que comportar.

Una vez definido el modelo se intentará aplicar lo que se conoce como \textit{algoritmo de rebaño}. Para poder realizar esto será necesario estudiar qué tipos de reglas son necesarias para lograr la organización de los agentes del sistema. Estas reglas deberán ser simple y se intentará que su cantidad sea tan reducida como sea posible, pudiéndose reusar y ampliar en trabajos futuros según la necesidad de modelado que se desean satisfacer. La meta será lograr identificar patrones similares a los observados en la naturaleza y de esta forma reconocer la emergencia de inteligencia en el sistema.

Por otro lado, podemos diferenciar interacciones entre agentes basadas en \textbf{potenciales}. Los modelos basados en este tipo de interacciones son \textbf{\textit{modelos continuos}}. Aquí se elegirá el uso de un potencial ya conocido y se intentará reconocer la emergencia de patrones y predecir estabilidad. En estos modelos el comportamiento de cada agente será el resultado de ecuaciones de movimiento que estarán basadas en el potencial usado.

Una vez identificados y definidos los modelos se procedió a estudiar e investigar trabajos previos que se relacionen con los modelos identificados. Luego se comenzó con el desarrollo de algoritmos de rebaño que permitan la emergencia de inteligencia en el sistema multi-agente. Pero podemos pensar que los algoritmos solo se basan en la administración de la información que cada agente posee, y esta información debe prevenir de algún lugar. La información puede ser entregada al agente por algún centro de control o el agente puede obtener esta información por sus medios. 

Lo que se desea en la rama de \textit{swarm intelligence} es que sea el agente, en base al uso de sensores que éste posee, quién \textit{sense u obtenga} la información necesaria para ser procesada por el algoritmo de rebaño. Es por esto que también se implementaron y estudiaron distos tipos de sensores


\newpage
\section{• Metodología}
Para realizar los estudios requeridos se comenzó con el desarrollo de distintos tipos de algoritmos de rebaño. Se decidió, en primer lugar, tratar de implementar un algoritmo basado en reglas que deberían seguir los agentes del sistema. Investigar si con un conjunto simple y bien definido de reglas se lograba llegar a formar un patrón u organización del sistema. Luego se cambiará esta forma de interacción por una basada en potenciales.

Se comenzó pensando con base a la reproducción de situaciones de la naturaleza tales como la el movimiento una bandada de aves y su organización. Vemos a menudo en la naturaleza cómo éstas forman grupos y se mueven realizando varios patrones complejos. Pero, ¿Qué tan complejo debe ser un sistema para comportarse de esa forma?, ¿Qué tan intelegente deben ser los agentes del sistema?, ¿Cómo hacer para sobreponerse a potenciales errores de agentes?.

Sabemos que los agentes de un sistema como el planteado no cooperan directamente con la formación del grupo, porque no tienen la información de que patrón formar o cual es su papel en dicha formación. Más aún, si un agente realiza lo que podemos pensar como un mal movimiento dentro de la formación del grupo o bien se va del grupo, el resto de los agentes no tienen la inteligencia necesaria para comprender cómo esa acción del agente afecta a toda la formación del grupo. 

En la naturaleza la información que tienen los agentes para saber cómo deben reaccionar proviene de su ADN. Es ahí donde tienen escritas las reglas a seguir, y estas reglas son tan básicas como saber que se tienen que mover en grupo, segui el grupo,  localizar comida, evitar el peligro, etc. Estas reglas simples son las que rigen su vida, junto con toda la información que puedan sensar en un momento particular. Por ejemplo: saben que deben moverse en grupo por lo tanto si un ave se encuentra sola y tiene un grupo de aves de su especie cerca, ésta tratará de unirse al grupo y moverse en el sentido que tiene el grupo, pero si para hacer ese movimiento tiene que atravezar un peligro, como algún predador, entonces es muy probable que, de poder sensar ese peligro, interrumpa su movimiento tratando de alejarse del peligro. Esto nos dice que dentro del conjunto de reglas que rige a un agente o grupo de agentes hay algunas con mayor prioridad que otras. En particular, son las reglas asociadas a la supervivencia las que suelen tener mayor prioridad, seguidas por un conjunto de reglas generales que se aplicarán de ser posible. Recordemos que lo que se trata de lograr es la evolución, y sin supervivencia no hay evolución. 

Para llegar a estos objetivos es vital la \textit{información}. La información y las desiciones tomadas en base a ella es lo que dirá qué grupos evolucionan y qué grupos no. Aquí es donde toma mayor importancia moverse en grupo y podemos ver las ventajas de la \textit{inteligencia de ganado}. Si un grupo de agentes logra organizarse, entonces éste dispondrá y se comportará de acuerdo a una información que es mayor y más rica que la que dispone cada agente en particular de dicho grupo. Información como la ubicación de la comida, evitar peligro, rutas para migrar, etc. Los agentes en particular no necesitan tener toda la información que tiene el grupo como unidad para favorecerse de ella. Es aquí donde hablamos de \textit{inteligencia de ganado}, esta información e inteligencia \textit{emerge} del grupo y a la vez no está localizada en ningún agente en particular sino en la suma de ellos, de pequeña información, ya sea erronea o no. En la naturaleza esto se ve de forma muy clara, para un animal que se separe de su grupo sus probabilidades de supervivencia y evolución son mucho menores a que si éste se hubiera quedado con su manada.

Por esto fue que se comenzó intentando definir un conjunto de reglas que permitan la formación de dicho grupo. Estas reglas sabemos que deben ser simples y algunas tendrán más prioridades que otras. Los \textit{algoritmos de rebaño} que tienen en cuenta las carecterísticas mencionadas son \textit{algoritmos discretos}. Veamos a continuación los modelos donde se aplican dichos algoritmos.

\newpage
\subsection{• Algoritmos de Rebaño}
Dentro de \textit{Swarm Intelligence} hay varias ramas de aplicación y estudio, desde video juegos hasta exploración de superficies. Pero dentro de estas ramas de aplicación, también podemos encontrar distintos algoritmos que generen esta \textit{Inteligencia de Ganado}. Estos algoritmos son conocidos como \textit{Algoritmos de Rebaño} y en nuestro caso veremos algoritmos que nos permitan organizar un grupo de agentes idénticos, predecir ciertos patrones y estabilidad del sistema.

Los algoritmos de rebaño, entonces, podemos definirlos como el motor de un sistema distribuido multi-agente. En \cite{sof-vs-hard-core} se define \textit{flock} \textit{como el movimiento coherente de un grupo de partículas auto-propulsadas que emerge de un conjunto de interacciones entre las partículas del grupo}. Este flujo y auto-gerenciación de agentes del sistema puede ser alcanzado de diferentes maneras, por lo que hay diferentes tipos de algoritmos. Para nuestro caso de estudio identificamos y analizamos dos tipos distintos de algoritmos de rebaño: \textit{\textbf{algoritmos de tipo continuo y discreto}}. También pueden haber híbridos de estos algoritmos, dando como resultado algoritmos \textit{mixtos}.

Los algoritmos \textit{\textbf{continuos}} son los que se basan en potenciales de interacción conocidos (Morse\cite{morse1}\cite{morse2}, Lennard-Jones\cite{L-J-1}\cite{L-J-2}, Van der Waals\cite{van-der-waals1}, etc.) que emulan la interacción entre partículas. En este tipo de algoritmos los agentes basan su movimiento en ecuaciones de movimientos, donde la fuerza que caracteriza la dirección y velocidad de cada agente viene definida por el gradiente del potencial elegido.

Por otro lado, los algoritmos \textit{\textbf{discretos}} son los que se basan en un conjunto pequeño y bien definido de reglas básica (del tipo \textit{no chocar, acercarse a los vecinos, etc}). En estos algoritmos los agentes tienen un conjunto de reglas que define su comportamiento, como algunas reglas pueden generar conflicto con otras, como en el caso de \textit{evitar colisiones} y \textit{agruparse} con sus vecinos, las reglas tienen una prioridad. Dicha prioridad se suele aplicar usando un órden para las reglas. Este órden puede llevar a que una o más reglas no se deban aplicar para una situación en particular.

Por último, los algoritmos \textit{\textbf{mixtos}} son los que mezclan reglas con el uso de potenciales para emular la relación entre partículas.


% para la Física es el  fue introducida hace tiempo por el físico Tamás Vicsek\cite{phys-flock}

\subsection{• Modelos Discretos}
Para poder aplicar un algoritmo de tipo discreto se usó un modelo de tipo discreto. El modelo que se deseaba construir debía centrarce en las reglas de los agentes. Por simplicidad se decidió utilizar un modelo en dos dimensiones. Los agentes no tendrán restricciones para moverse en el mismo, simplemente deberán seguir todos el mismo conjunto de reglas. Comenzarán de posiciones iniciales aleatorias y en cada tick de tiempo aplicarán todos sus reglas.

Para estudiar estos sistemas con interacción discreta se decidió usar la herramienta Netlogo. Veámosla a continuación.

\subsubsection{• Netlogo}

Netlogo nos ofrece un ambiente programable para poder simular fenómenos tanto sociales como naturales. Para simular sistemas, el lenguaje nos ofrece dos objetos: \textbf{\textit{turtles}} y \textit{\textbf{patches}}. A diferencia de la mayoría de los lenguajes orientados a objetos, el usuario no puede definir los objetos que quiera, sino que debe usar los ofrecidos por el lenguaje. 

Algo especialmente interesante sobre Netlogo es que permite dar instrucciones a sus objetos de forma concurrente. Facilitando la simulación y estudio de sistemas de interacción masiva y paralela. Como lo son los sistemas de rebaño, donde los agentes interactúan de forma local unos con otros de forma simultanea y el sistema en el que estos agentes se encuentran, si se modifica, también se hace de forma paralela.

Tanto las \textit{turtles} como los \textit{patches} pueden recibir instrucciones. Estas instrucciones se dan escribiendo \textit{procesos} y a su vez un conjunto de estos \textit{procesos} es lo que constituye y define un programa de Netlogo. Los procesos pueden ser de dos tipos: \textit{procesos de turtles} y \textit{procesos del observador}. Los procesos de las \textit{turtles} son el conjunto de instrucciones llevadas a cabo por las \textit{turtles}, de forma paralela. En un proceso de las \textit{turtles}, una \textit{turtle} puede pedirle a un \textit{patch} que ejecute cierto comando, por ejemplo, una \textit{turtle} en particular puede pedir al patch en donde esa \textit{turtle} está ubicada que actualize su estado a un nuevo valor.

Por otro lado, un proceso del \textit{observador} nos permite desde inicializar el programa hasta recolectar datos. Este tipo de procesos le puede pedir tanto a las \textit{turtles} como a los \textit{patches} que ejecuten comandos. Desde este tipo de procesos también se pueden crear o eliminar \textit{turtles}, definir las \textit{patches} que se usarán y monitoriar el estado de las mismas.

Luego, lo que se hace con este lenguaje para obtener una simulación es definir el tamaño del sistema, lo cual definirá los \textit{patches} usados. También se deben crear la cantidad de \textit{turtles} que creamos necesarias, que representan a los agentes del sistema. Luego hay que crear procesos que representen las reglas que deseamos que los agentes cumplan, como por ejemplo un proceso de \textit{alineación}, otro de \textit{separación} y otro de \textit{coherencia}. Así como también serán necesrios otros procesos auxiliares, para calcular posiblemente el conjunto de vecinos de una \textit{turtle} dada y también puede ser necesario saber obtener el vecino o \textit{turtle} más cercano para cada \textit{turtle}. Luego, tendremos algún proceso del tipo \textit{observador} que inicialize el sistema y les pida a las \textit{turtles} de forma paralela que ejecuten los procesos definidos para satisfacer las reglas en el orden que creamos necesario.


%Anteriormente hablamos de sistemas multi-agentes, en donde la interacción entre agentes estaba definida por un potencial, el potencial de Morse. Esta interacción, y los distintos valores tanto para las constantes que definen el potencial como para la cantidad de agentes determinaban las características de organización sistema. 

%Esta forma de definir la relación entre los agentes de un sistema no es la única. Su relación puede estar basada en un conjunto pequeño de reglas. Como vimos antes, los sistemas de ganado (swarm) constan de un grupo de agentes similares entre sí. Estos agentes suelen carecer de mucha complejidad o \textit{'inteligencia'}. Pero podemos ver en CITAR REFERENCIAS, basta con definir pocas reglas para que los agentes del sistema se organicen y veamos surgir patrones.

\subsubsection{• Reglas}
%Así como se eligió un potencial que defina la relación entre agentes para algoritmos continuos, también debemos definir un conjunto de reglas para el estudio de algoritmos discretos.

%In the mid 80's Craig Reynolds applied the principles of A-life to the phenomenon of birds flying in coordinated flocks. The challenge was to uncover simple rules that each bird (or boid) could follow that would produce flocking as an emergent behavior. Flocking is not a quality of any individual bird; it only emerges as a property of a group of birds. Each bird acts as an independent Agent and obeys the simple rules. Reynolds identified three simple rules for each boid to follow within some given global parameters, and the result was an uncanny facsimile of flocking behavior unfolding itself on his computer screen. The phenomenon has been applied repeatedly on screen in SIGGRAPH animations, for the penguins in Batman and the Wildebeest stampede in Lion King. To see the Java code behind boid

Cabe aclarar que las reglas se ajustan a distintos tipos de rebaños. No seguirán las mismas reglas una colonia de hormigas y una bandada de pájaros.

Las reglas que aquí se decidieron usar son 3: \textit{alineación, separación y cohesión}. Con estas simples reglas se puede crear un algoritmo de rebaño en donde los agentes del sistema se auto-organicen. Pasemos a explicar las reglas elegidas.

\begin{itemize}
\item \textbf{Separación:} Significa que los agentes tratarán de evitar choques o aproximaciones muy cercanas a otros agentes. Mientras más cerca están los agentes más aumenta la fuerza repulsiva entre ellos.

\item \textbf{Cohesión:} Significa que los agentes tenderán a moverse hacia otros agentes cercanos. Los agentes no quieren estar lejos de sus vecinos.


\item \textbf{Alineación:} Significa que los agentes tenderán a moverse en el mismo sentido en que se mueven los agentes a su alrededor(vecinos).

\end{itemize}

%Velocity is a vector quantity, referring to the combination of heading and speed. The manner in which the results from each of these behaviors is reconciled and combined is significant and is discussed in more detail later. Similarly,the meaning nearby in these rules is key to the flocking process. This is also discussed in more detail later, but generally one boid's awareness of another is based on the distance and direction of the offset vector between them.


La \textit{alineación} y la \textit{separación} son reglas complementarias. Una reorienta al agente mientras la otra lo aleja de una posible colisión con un vecino. Juntas permiten que los miembros de un rebaño puedan moverse libremente en el interiror del mismo sin que existan colisiones, aún estando sobre populado de agentes. La \textit{separación} es la necesidad de alejarse de un posible impacto. La \textit{separación} estática se basa en la posición relativa de los vecinos e ignora completamente su velocidad y dirección. Por otro lado, la \textit{alineación} se basa solo en la dirección en la que se mueven los vecinos e ignora completamente sus posiciones. Aquí vemos como se complementan ambas reglas. Pero la \textit{alineación}, a su vez, se puede ver como una forma predictiva de evitar colisiones ya que si un agente logra una buena \textit{alineación} con sus vecinos, entonces es poco probable que colisione con alguno de ellos. La \textit{alineación} hará que la distancia entre vecinos tenderá a mantenerse dentro de un rango fijo. Luego, la \textit{separación} estática sirve para establecer un mínimo de distancia requerido para el sistema, mientras que la \textit{alineación} tiende a mantenerlo.

La \textit{cohesión} es la regla que hace que los agentes quieran acercarse a otros agentes. Pero como los agentes tienen una percepción local del sistema, acercarse a otros agentes quiere decir juntarse con sus vecinos cercanos. Esta regla hace que el agente se quiera mover hacia el centro de masa de su grupo de vecinos. Por lo tanto, si un agente se encuentra cerca del centro del grupo y junto a muchos vecinos, se encontrará muy cerca del centro de masa del su rebaño y por ende la necesidad de moverse hacia el centro será mínima. Pero si el agente se encuentra en los límites externos del rebaño entonces tendrá una necesidad mayor de moverce hacia el centro de masa del rebaño por lo que se notará más el cambio de direccionamiento en su movimiento.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm]{vecinos.jpg} 
}
\caption{Vecinos de un agente. Vecinos de $i_0 = \lbrace i_1, ..., i_6\rbrace$. Vecinos de $i_6 = \lbrace i_0, i_1, i_4, i_5\rbrace$.}
\label{vecinos}
\end{figure}

Con estas reglas se puede crear un algoritmo de rebaño que simule por ejemplo una bandada de pájaros, un cardumen de peces, etc. Los agentes del sistema deberán ser capaces de acceder a su estado interno y también al estado local del sistema. Pues solo hará falta estos datos para que el sistema se organice, eh aquí la emergencia de inteligencia del rebaño. También será de vital importancia para nuestro algoritmo definir o poder identificar un conjunto de agentes cercanos, referenciados anteriormente como \textit{vecinos} y, a su vez, vamos a necesitar identificar dentro del conjunto de \textit{vecinos} al \textit{vecino} más cercano que tengamos, esto es para que podamos evitar colisiones aplicando la regla de \textit{Separación}.

Hasta aquí, nuestros algoritmo se basa en los vecinos de cada agente y el vecino más cercano para poder identificar que acción tomar en un caso determinado. En este tipo de algoritmos se puede dar el caso que alguna regla no sea compatible con otra, como sucede con \textbf{\textit{Separación y Cohesión}}. Mientras que la regla de \textit{Cohesión} le dice al agente que se tiene que acercar a sus vecinos, en algunas ocasiones la regla de \textit{Separación} le dirá que se aleje. Es, por lo tanto, necesario que nuestro algoritmo tenga en cuenta estas situaciones y para ello se deberá definir una prioridad que dirá que regla aplicar en las situaciones de incompatibilidad de reglas. 

Para nuestro caso de estudio es de mayor prioridad \textit{evitar colisiones con agentes}, por eso, cuando un agente se acerque demasiado a otro, la regla que se aplicará es la de \textit{Separación}, dejando de lado las otras dos reglas. El algoritmo se puede implementar de la siguiente manera:

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=5cm]{aplicar-reglas.jpg} 
}
\caption{Algoritmo de aplicación de reglas.}
\label{aplicar-reglas}
\end{figure}

\begin{enumerate}
\item Obtener vecinos (agentes que se encuentran en un radio de distancia $x$ )
\item Obtener el vecino más cercano. El agente más cerca del grupo obtenido en el punto anterior, si es distinto de vacío.
\item Pregunto si el vecino más cercano está muy cerca(menor a la distancia definida de separación)
\begin{itemize}
\item Si, entonces aplico solo la regla \textit{Separación}.
\item No, entonces aplico primero \textit{Alineación} y luego \textit{Cohesión}.
\end{itemize}


\end{enumerate}





%\subsubsection{• Acción/Reacción}




\newpage




\subsection{• Modelos Continuos}

Luego de haber implemento modelos de tipo discreto se comenzó a trabajar sobre modelos continuos. Aquí ya no encontramos reglas tan claras como en el caso anterior, sino que hay que definir una función que refleje la interacción entre los agentes. Pero como vimos antes, será necesario que dicha función nos permita identificar una \textit{atracción} entre agentes (para agruparlos) y una \textit{repulsión} entre los mismos (para evitar colisiones).

Para definir esta interacción entre agentes se debió elegir un potencial que refleje dicha interacción. El potencial elegido en el presente trabajo fue el potencial de \textit{Morse}. Este potencial habrá que parametrizarlo y estudiar los patrones o formas de organización que surgan del sistema.

La auto-organización de agentes es un área de estudio muy interesante \cite{morse1} \cite{morse2}, ya que los sistemas con un control no centralizado pueden exibir un poderoso y robusto comportamiento lo cual es un factor de interés para los científicos e ingenieros, sugiriendo estrategias para la construción de sistemas que sean robustos a las fallas, ya que cuando un sistema depende de un controlador centralizado, un daño en dicho controlador sería claramente un desastre sobre el sistema completo. 

Otra razón de interés para el estudio de \textit{Swarm Intelligence} es la necesidad de entender como los rebaños y la interacción entre agentes en la naturaleza ayuda a estos grupos a alcanzar  sus varias metas, entender como evoluciona el comportamiento de un rebaño y demás. Por otro lado, y de mayor importancia para nosotros, está el hecho de que estudiar la "\textit{Inteligencia de Ganado}" de la naturaleza nos lleva a nuevos algoritmos que tienen un amplio rango de aplicación. En particular, los algoritmos basados en \textit{Swarm Intelligence} proveen nuevas formas de resolver problemas de optimización complejos, nuevas formas de administrar y controlar el tráfico y redes de comunicación, lograr formas efectivas de generar simulaciones de rebaños y también estrategias e ideas para organizar grupos de robots orientados al cumplimiento de metas. Muy útil para potenciales futuras aplicaciones que pueden ir desde la manufacturación hasta la exploración espacial.

Aquí nos alinearemos con la rama de estudios que intenta predecir patrones y estabilidad en sistemas de rebaño. En particular, se puede distinguir en modelos de individuos auto-propulsados y con atracción de a pares (pairwise) e interacciones de repulsión, la emergencia de patrones morfológicos \cite{28}, \cite{29}, \cite{30}. Los patrones de formación que emergen en estos sistemas multi-agente pueden depender de distintos factores: \textit{interacción entre agentes}, \textit{cantidad de agentes}, \textit{propiedades del sistema}, \textit{etc}. Por eso, debemos definir ciertos valores, como por ejemplo de que definiremos la interacción entre agentes.

En nuestro caso, la definición de la interacción entre agestes se hizo usando el \textit{potencial de Morse}. La parametrización de dicho potencial, junto a características del sistema como posiciones iniciales de los agentes, sus velocidades y cantidad de agentes, trea aparejada la emergencia de patrones. Estos patrones pueden cumplir ciertos invariantes como la formación de grupos, anillos, sentido de rotación, etc. Por lo tanto se pueden definir tipos de patrones. Lo que nos interesaría es poder predecir la formación de determinados patrones. Pero a medida que la cantidad de agentes crece, muchos de estos patrones cambian.

Lo que se intenta es predecir la formación de patrones y la estabilidad de estos sistemas multi-agente. Para esto vamos a tomar un sistema formado por \textit{N} agentes idénticos que cuenten con auto-propulsión y experimenten una fuerza de fricción. Dicha propulsión estará dada de acuerdo al potencial que se elija, de modo que podemos generalizar la idea pensando en auto-propulsión biológica o también se podría construir un \textit{robot(boid)} motorizado que cumpla las mismas reglas derivadas del potencial. 

Para poder estudiar esta formación de patrones se decidió usar el ya conocido \textit{potencial de Morse generalizado}.


\subsubsection{• Potencial de Morse}
El potencial de Morse es una elección común para el modelado de la interacción de agentes en sistemas multi-agente. Este potencial está compuesto de dos términos: de atracción y de repulsión. La ecuación que define el potencial en su versión generalizada es la siguiente (\ref{morse}).

\begin{equation}
\label{morse}
U(\vec{x_1}) = C_{r}  e^{ \frac{ -|\vec{x_{1}} - \vec{x_{2}}|}{l_{r}}} - C_{a}  e^{ \frac{ -|\vec{x_{1}} - \vec{x_{2}}|}{l_{a}} }                                                                                                                                               
\end{equation}

donde $C_a$ y $C_r$ representan respectivamente las amplitudes de atracción y repulsión, y $l_a$ y $l_r$ representas respectivamente sus rangos de atracción y repulsión.

Como se puede notar, el potencial de una partícula $x_i$ se calcula tomando como referencia alguna otra partícula $x_j$ del sistema y su potencial de . Es por esto que a este tipo de potenciales se los denomina \textit{de a pares(pairwise)}. Cabe destacar que se podría elegir otro potencial de los denominados \textit{de a pares} y ver que incidencias tiene en el sistema, la predicción de formas emergentes y estabilidad del sistema.

En nuestro caso de estudio vamos a suponer un sistema de \textit{N} agentes. Cada uno de estos agentes \textit{sufrirá/sentirá} cierta atracción y repulsión de cada uno del resto de los \textit{N-1} agentes del sistema. Dicha atracción y repulsión será calculada usando la ecuación (\ref{morse}), dejando el potencial de cada agente determinado por el siguiente cálculo:

\begin{equation}
\label{potencial-individual}
U(\vec{x_i}) = \sum_{i\neq j} \biggl [C_{r}  e^{ \frac{ -|\vec{x_{i}} - \vec{x_{j}}|}{l_{r}}} - C_{a}  e^{ \frac{ -|\vec{x_{i}} - \vec{x_{j}}|}{l_{a}} } \biggr]                                                                                                                                               
\end{equation}
donde $x_i$ es el agente \textit{i-ésimo} del sistema.

Lo que se intenta es tratar de comprobar que se cumplas las predicciones de formaciones y de estabilización en los sistemas multi-agente que se muestran en \cite{self-propelled-particle}. Para esto debemos mostrar las ecuaciones de movimiento que rigen para las N partículas de nuestro sistema

\begin{equation}
 \vec{v_{i}} = \frac{\delta x_{i}}{\delta t}
\end{equation}

 \begin{equation}
 \label{fuerza}
 m \frac{ \delta \vec{v_{i}} }{\delta t} = (\alpha - \beta |\vec{v_{i}}|^{2} ) \vec{v_{i}} - \vec{\nabla}_{i} (\vec{x_{i}}) 
 \end{equation}

donde $\alpha, \beta > 0$ son valores efectivos de propulsión y fuerza de fricción. También se decidió por una cuestión de generalización y simplicidad hacer \textit{m=1} para todos los agentes del sistema. 

Para una fuerza independiente de la velocidad necesitaríamos $\alpha, \beta = 0$, lo que hace que las ecuaciones (\ref{potencial-individual})-(\ref{fuerza}) describan un \textit{sistema Hamiltoneano} con conservación de energía. También esperamos que se cumplan las condiciones de estabilidad para sistemas Hamiltoneanos. Dado un conjunto de \textit{N} partículas interactuando entre si, la energía potencial total del sistema \textit{U} se dice H estable si existe una constante $B \geq 0$ tal que $U \geq -NB$. Esto nos asegura que el conjunto de partículas no colapse cuando $N\rightarrow \infty$.

Los sistemas \textit{no H estables} se dicen \textit{catastróficos}, en cuyo caso a medida que N crece las partículas del sistema convergen agrupándose todas alrededor de un punto. Esto se desprende de que la energía total $U < 0$, por lo que la componente de atracción del potencial de Morse es la que domina, haciendo que las partículas se atraigan entre sí, concentrándose en un punto.

El diagrama de las formas y patrones que emergen del sistema de partículas cuya interacción está regida por el potencial de Morse como podemos ver en la \textbf{figura \ref{regiones}} (reproducción de la figura NR. 1 de \cite{self-propelled-particle}) se divide en regiones que son determinadas por las amplitudes relativas $C = \frac{C_r}{C_a}$ y $l = \frac{l_r}{l_a}$

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=5cm]{regiones-morse.png} 
}
\caption{Regiones Potencial de Morse. Reproducción de la figura NR. 1 de \cite{self-propelled-particle}}
\label{regiones}
\end{figure}

Como vemos en la figura \ref{regiones} las regiones catastróficas y H-estables están separadas por la curva $Cl^2 = 1$. 

\begin{itemize}
\item Región I: En esta región se forman grupos de agentes que viajan en forma circular al rededor de su centro de masa. Todos los agentes de un grupo tienen velocidades paralelas entre si y equivalentes a las de los demás agentes del sistema siendo la media $|v_i|^2 \sim \alpha / \beta$. Pero esta es una región catastrófica, lo que implica que a medida que el número de agentes crece $N \rightarrow \infty$ los agentes tienden a converger hacia un punto, debido al aumento de la fuerza de atracción. Veamos una captura de una simulación obtenida de esta región.
\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=7cm]{R_I2009_10_1_17_23_36.png} 
}
\caption{Región I. Parámetros: $N = 150; C_a = 1.0 ; C_r = 0.6 (C < 1)$ y $l_a = 1.0 ; l_r = 0.5 (l<1)$ con $\alpha = 1.0$ y $\beta = 0.5$.}
\end{figure}

\item Región II: Esta región también es catastrófica. Aquí $C = l$, y como vemos en \textbf{Figura \ref{regiones}} el patrón esperado es un círculo, cuyo radio disminuirá a medida que N crece. En \textbf{Figura \ref{region-ii}} vemos una captura de nuestra simulación para esta región.

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=7cm]{R_II2009_10_5_15_59_58.png} 
}
\caption{Región II. Parámetros: $N = 40; C_a = 1.0 ; C_r = 0.8$ y $l_a = 1.0 ; l_r = 0.8$ con $ \alpha = 1.0 ; \beta = 1.5$.}
\label{region-ii}
\end{figure}

\item Región III: Ésta región es catastrófica, con $ l > C$. Aquí aparecen grupos aunque no hay una separación bien definida entre los agentes. Estos se mueven siguiendo un patrón similar a un anillo. En Figura \ref{region-iii} vemos una captura de nuestra simulación.

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=7cm]{R_III2009_9_30_20_52_10.png} 
}
\caption{Región III. Parámetros: $N = 40; C_a = 1.0 ; C_r = 0.4$ y $l_a = 1.0 ; l_r = 0.7$ con $ \alpha = 1.0 ; \beta = 0.5$.}
\label{region-iii}
\end{figure}

\item Región IV: Ésta es otra región catastrófica, y como en el caso anterior $l > C$ pues ${C < 1 < l}$. Es por eso que aquí también vemos un grupo de agentes que tiende a organizarse en forma de anillo. 
----------------- FALTA FIGURA 5 DE SIMULACION ------------------

\item Región V: Aquí tenemos que $max \lbrace C,l \rbrace > 1$ y corresponde a una región H-estable. Aquí el potencial entre partículas del sistema se caracteriza por su componente de repulsión, minimizándose este cuando la $d_ij \rightarrow \infty$. Por lo que se espera que las partículas tiendan a divergir. En \textbf{Figura \ref{region-v}} vemos una captura de nuestra simulación.

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=7cm]{R_V2009_10_1_17_30_6.png} 
}
\caption{Región V. Parámetros: $N = 100; C_a = 0.5 ; C_r = 2.0 $ y $l_a = 0.5 ; l_r = 1.5$ con $ \alpha = 1.6 ; \beta = 0.5$.}
\label{region-v}
\end{figure}

\item Región VI: En esta región $ \lbrace 1/ \surd C < l < 1 \rbrace$. Es una región H-estable y en donde para un número finito de N, y valores intermedios de $\alpha / \beta$, las partículas ganan una energía cinética que es mucho mayor a la interacción entre partículas. Por lo que las partículas tienden a separarse. Por otro lado, para valores pequeños de $\alpha / \beta$ se espera que las partículas se organicen con separaciones bien definidas entre partículas.  En \textbf{Figura \ref{region-vi}} vemos una captura de nuestra simulación.

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=7cm]{R_VI2009_10_6_15_21_51.png} 
}
\caption{Región VI. Parámetros: $N = 100; C_a = 1.0 ; C_r = 2.0$ y $l_a = 1.0 ; l_r = 0.8$ con $ \alpha = 1.0 ; \beta = 0.5$.}
\label{region-vi}
\end{figure}

\item Región VII: En esta región $ \lbrace l < 1/ \surd C < 1 \rbrace$. Es una región catastrófica y como tal, cuando $N \rightarrow \infty $ el sistema converge. Pero para valores intermedios de $\alpha / \beta$ las partículas se mueven formando una dona, i.e, confinadas dentro de 2 radios(uno interno y uno externo). Estas partículas, para valores finitos de N, se pueden mover en sentido horario y anti-horario (coexistiendo ambos), dependiendo de las condiciones iniciales. En \textbf{Figura \ref{region-vii}} vemos una captura de nuestra simulación, donde se pueden ver dobles espirales, horarios y anti-horarios, que son un indicador de un potencial catastrófico.

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=7cm]{R_VII2009_10_6_15_24_42.png} 
}
\caption{Región VII. Parámetros: $N = 100; C_a = 0.5 ; C_r = 1.0$ y $l_a = 2.0 ; l_r = 0.5$ con $ \alpha = 1.6 ; \beta = 0.5$.}
\label{region-vii}
\end{figure}


\end{itemize}


\newpage
\subsection{• Sensores}
Ya hablamos de la organización y formación de patrones de en sistemas multi-agente cuyos algoritmos son \textit{continuos} o \textit{discretos}. Pero algo que tienen en común ambos es que de alguna forma interpretan el medio, ya sea de forma local o no. Algo que fue necesario en los dos tipos de algoritmos vistos fue la noción de distancia, poder calcular el vector $r_{ij}$, vector distancia desde el agente $i$ hasta el agente $j$.


Los agentes de los sistemas estudiados constan de sensores. Estos sensores son los que se encargan de captar información del medio, que luego será procesada, junto con información interna del agente, por los algoritmos de rebaño para producir alguna acción que tomará el agente.

Se estudiaron e implementaron en esta tesis sensores de distintos tipos: \textit{sensores basados en visibilidad geométrica y sensores basados en propagación en el medio}.

Dentro del primer grupo de sensores se implementaron \textit{sensores de distancia y sensores de visibilidad}. Mientras que dentro del segundo grupo de sensores se implementó \textit{sensor de Sonido}

Para que entendamos mejor el funcionamiento y la necesidad de los sensores veamos la siguiente Figura \ref{agent-structure}.

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=5cm, width=5cm]{AgentStructure.png} 
}
\caption{Diagrama de un agente, su interacción con el medio(vía sensores) y su actuación basada en lo censado y su estado interno}
\label{agent-structure}
\end{figure}


En esta Figura (\ref{agent-structure}) se muestra un agente (círculo), que tiene un vector de estados internos \textit{(is,internal states)}. Estos estados internos en un tiempo $t+1$ dependen tanto de sus valores en $t$ como de lo censado del \textit{sistema} en un tiempo $t$. Cada agente posee una cantidad $n$ de sensores \textit{(s)} que producen valores escalares en un tiempo dado, siendo $s_i(t)$ lo censado en el tiempo $t$ por el sensor $i$.

Los agentes tienen una forma de reaccionar ante ciertos estados, para esto poseen actuadores o efectores \textit{(a, actuators)} estos actuadores producen valores escalares, siendo $a_i(t)$ el valores del actuador $i$ para el tiempo $t$. Desde el punto de vista del agente, $s$ son los inputs y $a$ son los outputs. Por lo que podemos pensar en una función $f$ (pueden ser mas de una función) que toma los valores de los sensores y los valores de los estados internos y devolviendo valores de los actuadores y valores de los estados internos.

Adicionalmente los estados internos pueden tener una dinámica propia. Lo que se llama \textit{\textbf{reglas}}(o rules) en un agente son las funciones $f$.
 
\subsection{• Distancia}
El sensor de distancia es un sensor que fue necesario en todos los algoritmos de rebaño implementados. En los algoritmos de tipo \textit{continuo} es clara la necesidad pues el cálculo del \textit{potencial de Morse} se basa en la distancia de un agente a cada uno de los otros del sistema.

En los algoritmos de tipo \textit{discreto}, como vimos arriba, es necesario calcular los vecinos de cada agente, los agentes que se encuentran dentro de un radio determinado del agente. También era necesario calcular el vecino más cercano y poder saber la distancia a éste era vital para saber si se debía aplicar de la regla de \textit{Separación} o \textit{Alineación y Cohesión}.

Para el cálculo de la distancia nos basamos en que todos los sistemas multi-agente que se estudiaron fueron en dos dimensiones. Por lo que todo agente tiene su posición identificada en base a dos coordenadas (x, y), como así también su velocidad y aceleración.


\begin{figure}[h!t]
\centerline{
   \includegraphics[height=3cm, width=4cm]{vector_distancia.jpg} 
}
\caption{Vector distancia entre agentes $i$ y $j$.}
\label{vector-distancia}
\end{figure}


\subsubsection{• Potencial de Morse}
El \textbf{\textit{Potencial de Morse}} se usó para definir la relación entre los agentes del sistema. De esta forma queda bien definido como se comportan los agentes y es este potencial el que caracterizará el \textit{\textbf{flocking}} del sistema y los patrones que surjan.

Necesitamos algunos elementos o propiedades básicas, que son clave para definir un comportamiento de rebaño. La \textbf{separación} o distancia entre un agente $i$ y un agente $j$ del sistema, definida como $r_{ij}$. También es una regla general la de \textbf{evitar colisiones}, por lo tanto debemos definir un $r_{min}$, donde se desea mantener $r_{ij} < r_{min}$. También se desea cumplir que los agentes que se encuentran muy alejados dejen de interactuar entre si o su interacción sea suficientemente pequeña. Todas estas propiedades son tenidas en cuenta por el potencial usado.

Hay dos tipos de potenciales que se suelen usar para simular algoritmos de rebaño, estos son
\begin{itemize}
\item \textit{\textbf{Soft-core Potencials}}
\item \textit{\textbf{Hard-core Potencials}}
\end{itemize}
Ambos potenciales usan para sus cálculos el vector $\vec{r_{i,j}}$ (\textit{vector distancia del agente $j$ al agente $i$}). La diferencia principal entre ambos tipos de potenciales es la forma en que definen la energía para los agentes cuando este vector \textbf{\textit{tiende a cero}}($\vec{r_{i,j}} \to 0$).

Los potenciales del tipo \textit{\textbf{Hard-core}} son potenciales donde \textit{\textbf{la función que define la energía tiende a infinito cuando la distancia entre agentes tiende a cero}}.


\begin{equation}
\vec{r_{i,j}} \to 0 \Longrightarrow U( \vec{x_i} ) \to \infty
\end{equation}
Un ejemplo de este tipo de potenciales es el potencial de \textbf{Lennard-Jones (L-J)}, cuya definición es la siguiente

\begin{equation}
U^{L-J}(r) = 4\epsilon \Biggl [\biggl ( \frac{\theta}{r} \biggr)^{12} - \biggl ( \frac{\theta}{r} \biggr)^6 \Biggr]
\end{equation}


donde $r$ es el vector distancia, $\epsilon$ es la profundidad del potencial y $\theta$ es la distancia(finita) a la cual el potencial se define como cero. La ecuación está definida por un término de atracción y un término de repulsión, $r^{-6}$ y $r^{-12}$ respectivamente. En un sistema multi-agentes la ecuación que define el potencial para un agente podría definirse como a continuación

\begin{equation}
U^{L-J}_i(r) = \sum_{i\neq j} \epsilon \Biggl [\biggl ( \frac{r_{min}}{r_{ij}} \biggr)^{12} - \biggl ( \frac{r_{min}}{r_{ij}} \biggr)^6 \Biggr]
\end{equation}

donde $U^{L-J}_i$ es el potencial entre el agente $i$ y el resto de los agentes del sistema y $r_{ij}$ es la distancia entre el agente $i$ y el agente $j$. El mínimo de este potencial ocurre cuando $r = r_{min}$, que suele interpretarse como la separación deseada o esperada entre dos agentes. 


Los potenciales del tipo \textit{\textbf{Soft-core}} son potenciales donde la función que define la energía no diverge cuando la separación entre agentes tiende a cero, $r_{ij} \to 0$.

El \textit{\textbf{Potencial de Morse}} es un potencial de los del tipo \textit{\textbf{soft-cre potencial}}. Este potencial es comunmente usado en la física atómica y molecular. Como vimos antes (ecuación [\ref{potencial-individual}]), la definición generalizada que usamos de este potencial es la siguiente

\begin{equation}
U^M(\vec{x_i}) = \sum_{i\neq j} \biggl [C_{r}  e^{ \frac{ -|\vec{x_{i}} - \vec{x_{j}}|}{l_{r}}} - C_{a}  e^{ \frac{ -|\vec{x_{i}} - \vec{x_{j}}|}{l_{a}} } \biggr]                                                                                                                                               
\end{equation}

donde $U^M(\vec{x_i})$ es el potencial entre el agente $i$ y el restro de los agentes del sistema.


\subsubsection{• Algoritmo}
Para lograr la simulación podemos entonces tomar un grupo de agentes que sean idénticos entre sí. Estos agentes se deben ubicar en un espacio, en nuestro caso estarán en dos dimensiones (2D). Les vamos a dar una \textbf{posición inicial \textit{random} y velocidad inicial \textit{random}}.

Se supone un sistema sin límites, i.e, los agentes se pueden mover libremente por todo el espacio. Esto nos ayuda a que las simulaciones sean más parecidas al comportamiento natural, o capturen mejor lo que sucede en la realidad.

Un algoritmo que podemos seguir para la simulación es:
\begin{enumerate}
\item Setear las posiciones de los agentes, de forma \textit{\textbf{random}}.
\item Setear las velocidades iniciales de los agentes, de forma \textit{\textbf{random}}.
\item Actualizar las posiciones de los agentes. Teniendo en cuenta el \textit{\textbf{potencial de Morse}}.
\end{enumerate}

Las \textbf{posiciones iniciales son \textit{random} dentro de un \textit{círculo o cuadrado} con \textit{radio o lado}}\textit{(según corresponda)} \textbf{igual a $N*l_a$}, donde $ N $ en nuestro caso es 3 pero puede ser definido por el usuario según su deseo o necesidad y $l_a$ es el \textbf{rango de atracción del \textit{potencial de Morse}}. El centro del \textit{círculo o cuadrado} también se puede customizar según sea necesario. Aquí hay que tener en cuenta que como el ambiente o sistema donde se sitúan los agentes no tiene límites, \textbf{una \textit{posición inicial random} para los agentes donde el rango de valores sea muy grande ($>> l_a$) puede alejar demasiado a los agentes haciendo que éstos practicamente no sientan la interacción del resto de los agentes del sistema}. Fue por esta razón que se acotó la zona donde se eligen posiciones random.

También es importante acortar el rango de generación de velocidades iniciales, ya que puede estas pueden ser demasiado mayores a la fuerza que actúa sobre los agentes via la interacción del resto de los agentes del sistema. En este caso, los agentes se alejarán mucho y pueden perder mucha interacción con el resto de los agentes. También es bueno pensar que los agentes, al ser idénticos, uno desearía que tengan velocidades iniciales dentro de cierto rango acotado y no que algunos comienzen con velocidades demasiado altas y otros con velocidades muy pequeñas.

Para poder definir un rango para las velocidades iniciales se definió para cada simulación una \textit{\textbf{velocidad máxima}} haciendo uso de el \textit{\textbf{máximo del potencial de Morse (max\_potencial)}} para los parámetros de la simulación que se desea correr

\begin{mylisting}
\begin{verbatim}
max_potencial = C_r - C_a

# Asigno una energia cinetica maxima al sistema
if max_potencial < 0:
        MAX_KINETIC = 0.5 * -potencial
    else:
        MAX_KINETIC = 0.9 * potencial

# Defino la velocidad maxima de un agente
MAX_VEL = math.sqrt(2*MAX_KINETIC)
\end{verbatim}
\end{mylisting}

Luego podemos usar \textbf{MAX\_VEL} como tope de la velocidad inicial para generar una velocidad \textit{random}. Esta forma de elección de velocidad máxima es una y se puede cambiar para otras simulaciones.

Por último, para actualizar las posiciones necesitamos un bucle que para cada agente calcule el \textit{gradiente del potencial de Morse} y lo use para obtener la fuerza que afecta a ese agente. 

Para actualizar las posiciones se decidió usar el algoritmo de \textbf{Verlet Velocity}\cite{verlet_velocity}, un método numérico de integración de las ecuaciones de movimiento de Newton, muy popular en las \textit{simulaciones de dinámica de moléculas}.

Para lograr el algoritmo que simule el sistema multi-agente se tomó en cuenta que los \textit{boids o agentes} del sistema son todos idénticos. Por eso, se desición crear una clase que defina a estos \textit{agentes}, la clase \textit{\textbf{Agente()}}. Lo que hace este algoritmo es actualizar las posiciones, velocidades y aceleraciones para $t+ \Delta t$ usando los valores en tiempo $t$ de la siguiente manera

\begin{enumerate}
\item Actualizar $\vec{x}(t+ \Delta t) = \vec{x}(t) + \vec{v}(t)*\Delta t+ \frac{\vec{a}(t)(\Delta t)^^2}{2}$
\item Actualizar $\vec{v}( t+ \frac{\Delta t}{2}) = \vec{v}(t) + \frac{\vec{a}(t)*\Delta t}{2}$
\item Actualizar $\vec{a}(t+ \Delta t)$ usando el potencial.
\item Actualizar $\vec{v}(t+\Delta t) = \vec{v}(t+ \frac{\Delta t}{2}) + \frac{a(t+\Delta t )*\Delta t}{2}$
\end{enumerate}


\subsubsection{• Implementación}

Como vimos antes [\ref{fuerza}], al \textit{potencial de Morse} lo necesitamos para definir la fuerza que actuará sobre el agente. Lo que necesitamos calcular es el \textit{gradiente} de este potencial. Esto se debe calcular para cada \textit{agente} o \textit{boid} del sistema, por lo que se implementó un \textit{método} dentro de esta clase \textit{\textbf{Agente()}} que lo calcule. Este método se llamó \textit{\textbf{gradiente\_potencial\_morse()}} y se implementó de la siguiente manera

\begin{mylisting}
\begin{verbatim}
def gradiente_potencial_morse(self):
        global GLOBAL_VAR, agentes
        # Cargo parametros del potencial
        C_a = GLOBAL_VAR['C_a']
        l_a =GLOBAL_VAR['l_a']
        C_r =GLOBAL_VAR['C_r']
        l_r =GLOBAL_VAR['l_r']
        alpha =GLOBAL_VAR['alpha']
        beta =GLOBAL_VAR['beta']
        
        # Seteo a 0 las variables donde se guardara el valor del gradiente
        gradiente_coordenada_x = 0
        gradiente_coordenada_y = 0
        
        # Calculo factor repulsion y atraccion
        f_r = C_r/l_r
        f_a = C_a/l_a
        
        # Calculo el gradiente del potencial para todo agente distinto a 
        # mi mismo
        for agent in agentes:
            if agent.id == self.id:
                # Si soy yo continuo
                continue
            
            # Guardo distancia por coordenadas desde mi posicion al agente
            dist_x = self.pos[0] - agent.pos[0]
            dist_y = self.pos[1] - agent.pos[1]
            
            # Calculo el modulo de la distancia
            mod_r = math.sqrt(dist_x**2+dist_y**2)
            
            if (mod_r) < 1e-3:
                # Si la distancia es muy chica entonces no lo tomo en cuenta
                continue
            
            # Calculo los factores del potencial
            e_r = math.pow(math.e, -(mod_r)/l_r)
            e_a = math.pow(math.e, -(mod_r)/l_a)
            
            # Calculo la repelencia y atraccion
            rep = f_r*e_r
            atrac = f_a*e_a
            
            # Sumo a las coordenadas del gradiente lo correspondiente al 
            # agente que estoy teniendo en cuenta
            gradiente_coordenada_x += (-dist_x/mod_r)*( rep - atrac)
            gradiente_coordenada_y += (-dist_y/mod_r)*( rep - atrac)
        
        # Devuelvo valor del gradiente por coordenadas
        return [gradiente_coordenada_x,gradiente_coordenada_y ]
\end{verbatim}
\end{mylisting}




\subsubsection{• Verlet Velocity}
Los sistemas de rebaño estudiados en esta tesis son sistemas en dos dimensiones(2D). Donde cada agente puede ser identificado por dos coordenadas $\vec{r}(x_i) = (x_i,y_i)$. Pero estos agentes, con el tiempo, cambian su posición en la superficie ya que son afectados por el medio y el resto de los agentes. Luego, cada uno de los $N$ agentes tienen una posición en el tiempo $\vec{r}(x_i)(t)$ $\forall i :  0\leq i \leq N$ y una velocidad característica $\vec{v}(x_i)(t)$. Y como, ya sea via el potencial de Morse o reacciones a estímulos externos e internos, cada agente sufre una fuerza $\vec{f}(x_i)(t)$ en un tiempo dado.

Por lo tanto fue necesario integrar las ya conocidas ecuaciones de movimiento de Newton para poder calcular las trayectorias de los agentes. Para esto se decidió usar el método de integración Verlet, y de sus algoritmos se aplicó el \textit{Velocity Verlet}.



\subsubsection{• Simulaciones Hechas}


\subsubsection{• Patrones - Regiones}
\subsubsection{• Obervaciones}

\subsection{• Visión}
Otro de los sensores que se implementaron fue el sensor de visión. Lo que se intenta hacer con esto es acotar la funciones antes aplicadas sobre los agentes. Hasta ahora la actuación de un agente la podíamos pensar como una función ($f$) que depende de los $N$ agentes más el sistema ($E$).

\begin{equation}
[a_i, is_i] = \chi(x_1, x_2,..., x_{i-1},..., x_N) 
\end{equation}

donde $\chi$ es la función que define la actuación de agente $i$ $\forall i \in \{1, ..., N\}$. Por lo que esta función depende de los $N$ agentes. 

Ahora, si agregamos un sensor de visión, llamémoslo $\theta $, tal que:
\begin{equation}
\theta(i)=\{\ j \in \{1, ..., N\}:\ el\ agente\ j\ esta\ en\ el\ rango\ de\ vision\ de\ i\}
\end{equation}

y restringimos $\theta$ para que su resultado no sea siempre $\{1, ..., N\}$ entonces si aplicamos $\chi$ de la siguiente forma:
\begin{equation}
[a_i, is_i] = \chi \odot \theta(i)
\end{equation}

lo que estaremos haciendo es acotar el alcance de la función $\chi$.

Para lograr lo requerido se decidió utilizar la librería de \textit{VisiLibity} \cite{visiLibity}, escrita en C++.

\begin{figure}[h!t]
\centerline{
   \includegraphics[height=4cm, width=4cm]{area_vision.jpg} 
}
\caption{Rango de visión de un agente.}
\label{vision-agente}
\end{figure}

\subsubsection{• Algoritmo VisiLibity}
El algoritmo de visibilidad usado, \textit{Visilibity}, necesita primero que se defina un ambiente, esto se hace definiendo un polígono que representará dicho ambiente. Luego se pueden añadir o no polígonos que sean obstáculos para el observador(\textit{holes}), en nuestro caso de estudio no es de interés este punto.

Luego se definen al observador, que será un punto, y el resto de puntos o targets que en nuestro caso serían el resto de los agentes del sistema. Por último, se crea el polígono de visión del observador y se chequea que agentes están dentro de ese polígono.

Cabe destacar que en nuestro caso no hay obstáculos de visión, pero se los puede agregar sin complejidad alguna, y un agente no obstruye la visión de otro porque cada agente se piensa como un punto en el plano por lo que su área es tan pequeña que se decidió no tomarla como obstáculo de visión. Esta decisión también puede cambiarse definiendo un área para los agentes.

A continuación se mostrará un gráfico donde podremos ver un ejemplo del uso de la librería.

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=10cm, width=12cm]{visilibity-test.png} 
}
\caption{Test de librería \textit{VisiLibity}. Los polígonos rojos son obstáculos para la visión(holes), el punto azul en el centro es el observador, el rojo es un punto fuera del polígono de visión del observador y el punto azul se encuentra dentro del polígono de visión del observador.}
\end{figure}



\subsubsection{• Integración}
Hasta ahora los agentes no tenían ningún tipo de límite en su visión. Esto es porque no se había planteado dicho sensor. Con la creación de este nuevo sensor de visión, se intentará estudiar qué sucede cuando las funciones se ven acotadas por la visión del agente.

Trataremos de ver si algunos de los patrones conseguidos anteriormente se mantienen o se pierden con esta limitación. Así como el modo en que afecta al sistema multi-agentes regirse, por un lado con el potencial de \textit{Morse} y por otro lado con el sensor de visión.

Para hacer esto lo que se hizo fue calcular el potencial de \textit{Morse} pero para todos los agentes que se encuentren dentro del cono de visión definido previamente en el archivo de configuraciones.

\subsubsection{• Simulaciones Hechas}
\subsubsection{• Algoritmo Mixto - Visión/Distancia}
\subsubsection{• Simulaciones Hechas}
Las simulaciones hechas fueron especialmente sobre la \textit{\textbf{región catastrófica VII}}. Las simulaciones se hicieron de dos formas: \textit{usando la visión} antes vista y \textit{sin usar la visión}. 

Lo que usamos para definir la relación entre los agentes sigue siendo el potencial de Morse. Pero ahora, usando la visión se acota el alcance de la función. Por lo tanto, para cada conjunto de parámetros que se eligieron, se hicieron dos tipos de simulaciones: \textit{con visión} y \textit{sin visión}.

Veamos a continuación los patrones que emergen de estas simulaciones.

\begin{figure}[ht!]
   	\centering
   	%%----primera subfigura----
   	\subfloat[Agentes con visión de amplitud 300°.]{
   	\label{snapshot1:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=100.RVII/R_VII2009_11_4_21_35_32_snapshot_con_vision.png}}
   	%%----segunda subfigura----
   	\subfloat[Agentes sin sensor de visión.]{
 	\label{snapshot1:b}         %% Etiqueta para la segunda subfigura
  	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=100.RVII/R_VII2009_11_7_17_20_55_snapshot_sin_vision.png}}\\[20pt]
	\caption{Patrones de simulaciones de la \textbf{región VII} de \cite{self-propelled-particle}. Parámetros para ambos: $C_a = 0.5 ; C_r = 1.0 ; l_a = 2.0 ; l_r = 0.5 ; \alpha = 1.6 ; \beta = 0.5$ y N=100(cantidad de agentes).}
   	\label{snapshot1}                %% Etiqueta para la figura entera
\end{figure}

Lo que podemos notar en la \textbf{Figura \ref{snapshot1:a}} es que sin visión, para los parámetros elegidos de la región VII de \cite{self-propelled-particle}, lo que antes era catastrófico ah dejado de serlo. Mientras que con visión, como vemos en \textbf{Figura \ref{snapshot1:b}} sigue siendo catastrófico y emerge el mismo patrón que en la región VII de \cite{self-propelled-particle}.


También se hizo un análisis de las distancias de los agentes en ambos casos. Para esto, se hizo histogramas de las posiciones de los agentes cada intervalos regulares de tiempo. Estos histogramas están normalizados, i.e, la cuenta de los agentes en un bin está normalizada para formar una densidad de probabilidad. Dado que tenemos una función de densidad de probabilidad, la integral del histograma debería ser 1. Esto se hizo para ver como se comporta la distribución de la densidad en cada caso a lo largo del tiempo.
\begin{figure}[ht!]
	\centering
   	% ----primer subfigura----
	\subfloat[Simulación con visión.]{
	\label{dist-time:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=100.RVII/R_VII2009_11_4_21_35_32_log_Dist_vs_Time_con_vision.png}}
	% ----segunda subfigura----
	\subfloat[Simulación sin visión]{
	\label{dist-time:b}         %% Etiqueta para la segunda subfigura
	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=100.RVII/R_VII2009_11_7_17_20_55_log_Dist_vs_Time_sin_vision.png}}\\[20pt]
   	\caption{Plot de distancia entre histogramas vs tiempo. Los patrones de simulaciones son idem Figura [\ref{snapshot1}].}
   	\label{dist-time1}                %% Etiqueta para la figura entera
\end{figure}

Como podemos ver en la \textbf{Figura [\ref{dist-time:a}]}, la distribución de los histogramas tiende a estabilizarse en el tiempo. Entonces la función de distribución se estabiliza aunque los agentes se separen.


A continuación veamos una simulación con \textbf{N=150} agentes,

\begin{figure}[ht!]
   	\centering
   	%%----primera subfigura----
   	\subfloat[Agentes con visión de amplitud 300°.]{
   	\label{snapshot2:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=150.RVII/R_VII2009_11_11_16_52_39.png}}
   	%%----segunda subfigura----
   	\subfloat[Agentes sin sensor de visión.]{
 	\label{snapshot2:b}         %% Etiqueta para la segunda subfigura
  	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=150.RVII/R_VII2009_11_12_16_18_58_sin_vision.png}}\\[20pt]
	\caption{Patrones de simulaciones de la \textbf{región VII} de \cite{self-propelled-particle}. Parámetros para ambos: $C_a = 0.5 ; C_r = 1.0 ; l_a = 2.0 ; l_r = 0.5 ; \alpha = 1.6 ; \beta = 0.5$ y N=150(cantidad de agentes).}
   	\label{snapshot2}                %% Etiqueta para la figura entera
\end{figure}

En la \textbf{Figura \ref{snapshot2:a}} podemos ver que con los parámetros usados y sensor de visión los agentes dejan de formar el patrón que antes formaban para dichos valores. Por otro lado, si quitamos la visión (\textbf{Figura \ref{snapshot2:b}}) vemos como se comienza a formar la dona característica de dicha región.

Con respecto a la distribución de los agentes, miramos las distancias entre los histogramas. Lo que vemos en la \textbf{Figura \ref{dist-time2:a}} es en la simulación \textit{con visión} la distancia entre histogramas tiende a 0, lo que indica que la distribución de los agentes se estabiliza. Esto posiblemente se deba a la escasa energía cinética que hay en el sistema.

Por otro lado, en la \textbf{Figura \ref{dist-time2:b}} vemos una función con \textit{picos} en los primeros segundos, que indican cambios abruptos de la distribución de los agentes en el sistema para luego continuar con cierto ruido. Si bien estrictamente no se estabiliza la función, los rangos de oscilación son muy pequeños.
\begin{figure}[ht!]
   	\centering
   	%%----primera subfigura----
   	\subfloat[Agentes con visión de amplitud 300°.]{
   	\label{dist-time2:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=150.RVII/R_VII2009_11_11_16_52_39_log_Dist_vs_Time_con_vision.png}}
   	%%----segunda subfigura----
   	\subfloat[Agentes sin sensor de visión.]{
 	\label{dist-time2:b}         %% Etiqueta para la segunda subfigura
  	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=150.RVII/R_VII2009_11_12_16_18_58_log_Dist_vs_Time_sin_vision.png}}\\[20pt]
	\caption{Distancia entre histogramas vs tiempo de la \textbf{región VII} de \cite{self-propelled-particle}. Parámetros idem Figura [\ref{snapshot2}].}
   	\label{dist-time2}                %% Etiqueta para la figura entera
\end{figure}


A continuación veamos la energía cinética media del sistema ($\overline{K}$). La \textbf{Figura \ref{kinetic2}} nos muestra que con visión la energía cinética tiene a bajar, acorde con la falta me velocidades que vimos en en la \textbf{Figura \ref{snapshot2:a}}. Mientras que en la \textbf{Figura \ref{kinetic2:b}} vemos una tendencia a la suba de la energía cinética con una oscilación cuyo rango se achica con el tiempo. Esto nos dice que podemos esperar una estabilización de la energía cinética media marcada por un rango de oscilación acotado.

\begin{figure}[ht!]
   	\centering
   	%%----primera subfigura----
   	\subfloat[Agentes con visión de amplitud 300°.]{
   	\label{kinetic2:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=150.RVII/R_VII2009_11_11_16_52_39_log_k_vs_time_con_vision.png}}
   	%%----segunda subfigura----
   	\subfloat[Agentes sin sensor de visión.]{
 	\label{kinetic2:b}         %% Etiqueta para la segunda subfigura
  	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=150.RVII/R_VII2009_11_12_16_18_58_log_k_vs_time_sin_vision.png}}\\[20pt]
	\caption{Energía cinética vs tiempo de la \textbf{región VII} de \cite{self-propelled-particle}. Parámetros idem Figura [\ref{snapshot2}].}
   	\label{kinetic2}                %% Etiqueta para la figura entera
\end{figure}


En la \textbf{Figura \ref{radio2}} vemos gráficos del radio. El radio se calcula con centro en el centro de masa de los agentes.

\begin{figure}[ht!]
   	\centering
   	%%----primera subfigura----
   	\subfloat[Agentes con visión de amplitud 300°.]{
   	\label{radio2:a}         %% Etiqueta para la primera subfigura
	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=150.RVII/R_VII2009_11_11_16_52_39_log_r_vs_time_con_vision.png}}
   	%%----segunda subfigura----
   	\subfloat[Agentes sin sensor de visión.]{
 	\label{radio2:b}         %% Etiqueta para la segunda subfigura
  	\includegraphics[width=0.55\textwidth]{./simulaciones-vision/n=150.RVII/R_VII2009_11_12_16_18_58_log_r_vs_time_sin_vision.png}}\\[20pt]
	\caption{Radio medio entre agentes vs tiempo de la \textbf{región VII} de \cite{self-propelled-particle}. Parámetros idem Figura [\ref{snapshot2}].}
   	\label{radio2}                %% Etiqueta para la figura entera
\end{figure}

Se puede ver en la \textbf{Figura \ref{radio2:a}} que en un primer momento los agentes comenzaron a converger a un punto, comportamiento que indica una situación catastrófica del sistema. Pero luego hay un cambio muy abrupto en el comportamiento del sistema, después de los 2 segundos, que hace que los agentes divergan. Aunque la distancia media del radio final es suficientemente chica, lo cual quiere decir que los agentes están muy agrupados, vemos que su tendencia es a alejarse(diverger) y no a mantener un R medio estable, i.e., formar la figura de la dona.

Sin embargo, en la \textbf{Figura \ref{radio2:b}} vemos como el R medio oscila entre un rango definido de valores. Pero de a poco esa oscilación se va haciendo más pequeña, tendiendo hacia cierta estabilidad del R medio, propiedad necesaria para la formación de la figura de la \textit{dona}, acorde al patrón de la región VII de \cite{self-propelled-particle}. La oscilación nos muestra una posible expansión y compresión de la dona, dentro de un \textit{r\_min} y un \textit{r\_max}.
 


\newpage
\subsubsection{• Patrones - Regiones}
\newpage
\subsubsection{• Obervaciones}
\newpage
\subsection{• Sonido}

Otro de los sensores que se implementó es un sensor que simula el sonido. Para esto debió cambiarse el entorno al que pertenecen los agentes, debido a que por su simplicidad no permitía implementar una manera optimizada de propagación. Lo que se implementó y estudió fue la propagación de ondas de presión en un medio. Esta presión será generada por cada agente en cada intervalo de tiempo. 

Por simplicidad, y siguiendo la uniformidad que mantiene el sistema, los agentes generarás la misma presión. Luego, no habrá distinción entre agentes. La cantidad de presión generada por cada uno se determinó empíricamente, y puede cambiarse según se considere necesario.


\subsubsection{• Propagación en Medio Material}

Para propagar esta presión se decidió simular el medio usando un Autómata Celular(CA). Los CA son una excelente herramienta para las simulaciones, están fuertemente ligados a la inteligencia artificial por la flexibilidad y simplicidad para simular sistemas complejos y de muchos estados.

\subsubsection{• CA}
Un \textit{Autómata Celular} es una grilla o matriz de celdas o células, que se rige en base a reglas generales que se aplican a todas las celdas/células. Gran parte de su popularidad se basa en que con un conjunto chico de reglas se pueden simular sistemas complejos. Los \textit{CA} también se encuentran muy ligados a la inteligencia artificial, porque muestran el concepto de \textit{emergencia}, i.e, como a partir de interacciones locales emergen patrones en el sistema global.

El estado actual $(t)$ de un CA se define en base al estado que tengas las celdas que lo componen. Mientras que el estado en el próximo paso de tiempo $(t+1)$ depende del estado en $t$ y la aplicación de las reglas para cada celda. Estas celdas definen su estado en base a un conjunto de valores que pueden tomar, previamente definido. Sea $\lbrace \eta_1, \eta_2, ....,\eta_n \rbrace$ el conjunto de estados que puede tomar cada celda del \textbf{CA}. 

Todas las celdas que componen el CA cambian de estado al mismo tiempo, de forma síncrona. Es decir, las reglas se aplican a todas las celdas al en el mismo instante de tiempo, y el nuevo valor de las celdas depende de la aplicación de las reglas y el estado de los vecinos de la celda en ese instante. Esto es:


\begin{equation}
\varepsilon_0 = Estado\ inicial;\ \\\
\\\varepsilon_1 = \xi(\varepsilon_0);\ \\
\varepsilon_2 = \xi(\varepsilon_1);\ \\
\varepsilon_3 = \xi(\varepsilon_2);\ \\
...;\ \\
\varepsilon_{n+1} = \xi(\varepsilon_n)
\end{equation}
donde $\varepsilon_i$ es el estado $i$ y $\xi$ es la función que aplica el cambio de estado al \textbf{CA}.

La aplicación de la función $\xi$ es el resultado de aplicar de forma síncrona las reglas a cada celda del \textbf{CA}. Esta aplicación de reglas a una celda depende del estado de la celda en ese instante de tiempo y el de sus \textit{vecinos}. Hay dos tipos definidos de \textit{\textbf{vecindades(neighbourhoods)}} para un \textbf{CA} de \textit{dos dimensiones}, la \textbf{vecindad de \textit{Von Neumann}} y la \textbf{vecindad de \textit{Moore}}. La \textbf{vecindad de \textit{Von Neumann}} consta de los vecinos al norte, sur, este y oeste de cada celda, cuatro vecinos por celda. Mientras que la \textbf{vecindad de \textit{Moore}} consta de ocho vecinos, los cuatro de \textbf{\textit{Von Neumann}} más los cuatro diagonales. Definámoslo más formalmente.

\begin{equation}
\Theta(\varphi_{i,j}) = \lbrace \varphi_{i-1,j}, \varphi_{i+1,j}, \varphi_{i,j-1}, \varphi_{i,j+1} \rbrace
\end{equation}

\begin{equation}
\Gamma(\varphi_{i,j}) = \lbrace \varphi_{i-1,j-1}, \varphi_{i-1,j}, \varphi_{i-1,j+1}, \varphi_{i,j-1}, \varphi_{i,j+1}, \varphi_{i+1,j-1}, \varphi_{i+,j}, \varphi_{i+1,j+1} \rbrace
\end{equation}

siendo $\Theta$ la función que define la vecindad de \textbf{\textit{Von Neumann}} y $\Gamma$ la función que define la vecindad de \textit{\textbf{Moore}}. Podemos ver una ilustración en la \textit{Figura \ref{vecindades}}.

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=3.5cm, width=5cm]{vecindades-ca.jpeg} 
}
\caption{Vecindades de CA. Figure 1 de \cite{ca-spreadsheet} }
\label{vecindades}
\end{figure}


El siguiente estado de una celda, entonces, lo podemos definir más claramente con la siguiente ecuación (\ref{next-state}):

\begin{equation}
\label{next-state}
\phi(\varphi_{i,j},t+1) \in \lbrace \eta_1, \eta_2, ....,\eta_n \rbrace
\end{equation}

donde $\varphi_{i,j}$ definen unívocamente una celda en la grilla y $\phi$ es la función que refleja las reglas del autómata, dando como resultado el estado o valor que tomará la celda $\varphi_(i,j)$ en el tiempo $t+1$. El conjunto $\lbrace \eta_1, \eta_2,...,\eta_n \rbrace$ es el conjunto que define los valores que puede tomar cada celda.

Por lo tanto, podemos definir un autómata celular como un sistema que se compone de: \textit{un estado inicial, es espacio discreto, un tiempo discreto, un conjunto de estados posibles para cada celda, un conjunto de reglas y, si la matriz no es infinita, condiciones de frontera (que definen reglas a aplicar para las celdas que se encuentran en las fronteras de la matriz)}

\subsubsection{• Conways's Game of Life}

Como apéndice extra se implementó el \textit{\textbf{Juego de la vida (Game of Life)}}, probablemente el CA más popular que existe, es un autómata celular creado por el matemático John Conways. Podemos leer información general del \textit{Juego de la Vida} en \cite{paul-collahan-math}. 

En este CA el conjunto de valores o estados posibles que puede tomar cada celda es $\lbrace viva,\ muerta\rbrace$, o lo que es lo mismo, $\lbrace 1,\ 0 \rbrace$, $\lbrace negro,\ blanco \rbrace$. 

Las reglas de este CA son:

\begin{enumerate}
\item Una celda \textbf{muerta} y con \textit{exactamente} 3 vecinos \textbf{vivos}, \textbf{vive} en la siguiente generación (\textit{reproducción}).
\item Una celda \textbf{viva} con 2 o 3 vecinos \textbf{vivos} permanece viva la siguiente generación (\textit{persistencia}).
\item Una celda \textbf{viva} con 4 o más vecinos \textbf{vivos} \textbf{muere} la próxima generación (\textit{por superpoblación}).
\item Una celda \textbf{viva} con menos de 2 vecinos \textbf{vivos}, \textbf{muere} en la próxima generación (\textit{por aislamiento})
\end{enumerate}


El \textit{\textbf{Juego de la Vida}} de Conway ha sido ampliamente estudiado para tratar de entender \textit{\textbf{complejidades emergentes}} y \textit{\textbf{sistemas auto-organizados}}, tal como nos intereza estudiar en este trabajo. Este autómata nos muestra la emergencia de patrones o comportamientos muy complejos que surgen a partir de un conjunto de reglas conocidas y simples.

Otro de los puntos de estudio de este CA es que tiene la complejidad de una \textit{\textbf{máquina universal de Turing}}\cite{paul-conway-turing}, lo que hace que sea \textit{\textbf{Turing-completo}}. Por lo que se puede usar para calcular cualquier \textit{\textbf{función o lenguaje recursivo}}, que según sostiene la \textit{\textbf{tesis de Church-Turing} "todo lo computable es computable por una máquina de Turing"}. 

Luego, el \textit{Juego de la Vida} nos permite resolver exactamente todos los problemas que se pueden resolver por un \textit{algoritmo}.


\subsubsection{• Implementación}

El lenguaje usado fue el mismo que para las simulaciones, Python. Para la implementación de un CA se pueden usar diferentes tipos de datos. En el caso de estudio se decidió definir nuestra clase \textit{Matrix} que guarda como atributos internos la cantidad de filas y columnas y también la matriz en si que es una lista de listas (un \textit{array} de \textit{arrays}). Cada una de las posiciones de este objeto \textit{Matrix} está ocupada por un entero, 0 o 1 según la celda esté muerta o viva respectivamente.

A continuación la definición de la clase \textit{Matrix} en Python:

\begin{mylisting}
\begin{verbatim}
class Matrix():
    """Creo una matriz que sera una lista de listas
    la lista inicial tendra en cada posicion las filas
    de la matriz:
    Ejemplo de matriz 4xn
        [fila1, fila2, fila3, fila4]
    Donde fila_i es una lista de longitud n"""
    
    def __init__(self, rows, cols):
        self.cols = cols
        self.rows = rows
        
        # Inicializo matriz
        self.matrix = []
        
        for i in range(rows):
            # Creo una fila nuevo
            row = []
            
            for j in range(cols):
                # Lleno la fila con 0 en cada celda
                row.append(0)
            
            self.matrix.append(row)
\end{verbatim}
\end{mylisting}

Debido a que el cambio de estado de un CA de un momento $t$ al $t+1$ se basa en la aplicación de reglas de forma síncrona a todas las celdas de la matriz, una de las opciones de implementación para actualizar su estado es usando dos matrices, una para el tiempo $t$(\textit{matrix}) y otra para el tiempo $t+1$(\textit{new}), donde la segunda matriz ((\textit{new})) obtenga los valores de cada celda a partir de recorrer todas las celdas de la matriz (\textit{matrix}) y aplicar las reglas. A continuación se muestra la función de actualización de estado de la matriz:

\begin{mylisting}
\begin{verbatim}
def update(matrix):
    new = Matrix(matrix.rows, matrix.cols)
    
    for i in range(1, matrix.rows+1):
        for j in range(1, matrix.cols+1):
            vivir = rules(matrix, i, j)
            if vivir:
                new.set_value(i,j, VIVO)
                
    return new
\end{verbatim}
\end{mylisting}

donde \textit{rules()} obtiene los vecinos \textit{vivos} de \textit{(i,j)}. Por lo tanto para actualizar \textit{matrix} basta con,

\begin{mylisting}
\begin{verbatim}
matrix = update(matrix)
\end{verbatim}
\end{mylisting}

con esto ya estamos en condiciones de implementar el \textit{Juego de la Vida} con un bucle que actualize la matriz en cada pasa de tiempo.

Pero hasta aquí tenemos una matriz con ceros y unos, por lo que se decidió usar la librería PyGame para implementar el juego de la vida de forma gráfica. Para lograr esto, se hizo uso de la clase \textit{Sprites} de PyGame en la definición de una nueva clase, la clase \textit{Cell}.

\begin{mylisting}
\begin{verbatim}
# Celda de automata celular usando Sprites de Pygame
class Cell(pygame.sprite.Sprite):
    
    def __init__ (self, color=None, size=None, pos=None):
        global N, cells
        # Inicializo Sprite
        pygame.sprite.Sprite.__init__ (self) 
        
        if size == None:
            size = (SIZE,SIZE)
        image = pygame.Surface(size)
        image = image.convert()
        
        if color==None:
            # 0 = blanco, 1 = negro ; 0 = muerto, 1 = vivo
            color = 0
        self.color = color
        self.new_color = color
        # Lo lleno del color correspondiente
        if color: 
            image.fill( BLACK )
        else:
            image.fill( WHITE )
            
        self.image = image
        self.rect = image.get_rect()
        
        self.pos = (0,0)
        if pos != None:
            self.pos = pos
        self.rect.topleft = pos
\end{verbatim}
\end{mylisting}

Para mantener separada la parte numérica de la parte gráfica se creó una nueva matriz, separada, que agrupa todos los \textit{Sprites}, cuyas posición en la ventana creada es una al lado del otra y el color que toma (blanco o negro) depende de si la celda de la matriz \textit{matrix} está muerta o viva respectivamente. Por lo tanto esta matriz de \textit{Sprites} de Pygame se adapta al estado que tiene el CA simulado numericamente.


\subsubsection{• CA for pressure}

Para simular la propagación de \textit{presión} en el medio, que será necesaria para implementar un sensor de sonido para los agentes, se usó un \textbf{CA}. Este \textbf{CA} representa el medio en el que se encuentran los \textit{agentes o boids} y cada celda de este \textbf{CA} es una porción del sistema.

Podemos pensar en nuestro sistema de modo matricial. Ahora nuestro sistema está discretizado, i.e, un punto en el plano ahora está representado por una celda y esta celda a su vez tiene 8 vecinos, 4 con los que comparte un lado y 4 con los que comparte un vértice. Esta forma de discretizar el sistema nos ayudan mucho para mantener un control de las propiedades del sistema.

Esta forma de simular el sistema es muy útil tanto para juegos como para simulaciones de distintos medios. Por ejemplo, si pensamos en un medio homogéneo lleno de \textit{aire} entonces cada celda representa una pequeña porción de este medio, donde todas las celdas tienen la misma propiedad. Todas las celdas se comportan respetando las reglas que queremos que cumpla este \textit{aire} que queremos modelar.

También podemos modelar sistemas más complejos. Supongamos que deseamos propagar fuego o presión  por ese medio, entonces solo nos basta estudiar como es que se propaga en este medio y aplicar esas reglas para las celdas del \textbf{CA}. Si queremos ahora agregar paredes u otros materiales, pensamos que basicamente tenemos el mismo medio solo que ahora las propiedades de estas celdas son distintas. Donde sea que se ubiquen estos nuevos objetos solo debemos cambiar las propiedades de las celdas que ocupan esas posiciones.


Para implementar este nuevo \textbf{CA} se definió una nueva clase en Python, la clase \textit{\textbf{Matrix()}}. Veamos a continuación la definición del método \textbf{\textit{\_\_init\_\_}}

\begin{mylisting}
\begin{verbatim}
class Matrix():
    """Creo una matriz que sera una lista de listas
    la lista inicial tendra en cada posicion las filas
    de la matriz:
    Ejemplo de matriz 4xn
        [fila1, fila2, fila3, fila4]
    Donde fila_i es una lista de longitud n"""
    
    def __init__(self, rows, cols):
        '''Inicializa una matriz de NxM donde N=rows y M=cols. 
        Todas las celdas se inicializan en 0'''
        self.cols = cols
        self.rows = rows
        
        # Inicializo matriz
        self.matrix = []
        
        for i in range(rows):
            # Creo una fila nuevo
            row = []
            
            for j in range(cols):
                # Lleno la fila con 0 en cada celda
                celda = Celda()
                row.append(celda)
            
            self.matrix.append(row)
\end{verbatim}
\end{mylisting}

como se puede ver en cada lugar de la matriz hay un objeto del tipo \textit{\textbf{Celda()}}. Este objeto está definido de la siguiente manera:

\begin{mylisting}
\begin{verbatim}
class Celda():
    '''Define la clase que se usa como celda de una matriz.'''
    def __init__(self, pressure=0, new_pres=0):
        '''Inicializa todos los valores con pressure y los new con new_pressure.'''
        self.visitado = False
        self.visitas = []
        self.pressure = pressure
        self.new_pressure = new_pres
\end{verbatim}
\end{mylisting}


\subsubsection{• Algoritmo}
Para propagar la presión en el medio se siguió el paper \cite{ca-physical-modeling}. En esencia, lo que se hizo fue tomar al sistema, el ambiente donde viven los agentes, como una gran matriz. Esta matriz está llena de celdas, que representan cada punto del plano del ambiente. Estas celdas son las que se relaciona entre sí y guardan la información local del sistema. En nuestro caso, la presión en ese punto.

Entonces, tenemos una matriz cuyas celdas se relacionan con sus celdas vecinas siguiendo ciertas reglas que se deben determinar. Pero esto no es más que un CA y reglas que definen el comportamiento de sus celdas. Es por eso que se dicidió usar CA en este trabajo.

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=5cm, width=6cm]{matrix-ambiente.png} 
}
\caption{Sistema interpretado como matriz.}
\label{matriz-ambiente}
\end{figure}

Como se puede notar, usando esta forma de interpretación no sería dificil extenderlo hacia un ambiente donde haya obstáculos. Donde los obstáculos son objetos inertes que no permiten la propagación de presión. Son celdas que obstruyen la propagación normal, ya sea sea de forma total o parcial la obstrucción. Esto haría que el sistema no sea más de una composición homogenea. 

Para hacer esto podemos identificar celdas \textbf{vivas} de \textbf{inertes} o podemos tener un valor que defina la cantidad de flujo que permiten pasar. Es decir, un grado de permeabilidad para las celdas. Esto puede ser de mucha utilidad para estudios de sistemas más complejos, o bien para juegos donde se necesite modelar un medio complejo, con distintos materiales.

A continuación un ejemplo de un sistema con celdas inertes que no permiten la transmisión de flujo.

\begin{figure}[h!t]
\centerline{
%   \includegraphics[height=5cm, width=6cm]{matrix-cells-inert.png} 
}
\caption{Sistema con celdas que impiden el flujo de presión. Con \textit{azul} identificamos las celdas vivas del sistema y con \textit{gris} las inertes. Podría ser una pared que obstruye el flujo de presión del aire, donde el aire se identifica con las celdas \textit{azules}.}
\label{matriz-ambiente}
\end{figure}

Una de las desiciones que se tomó es usar la vecindad de \textit{Von Neumann}, i.e los vecinos al norte, sur, este y oeste de la celda. 

Para simular la propagación de presión en este medio definido como un CA, lo que debemos hacer es definir reglas que demuestren el comportamiento que deseamos. Claramente cada celda va a tener cierta magnitud de presión, y en la próxima generación del CA esta presión se debe propagar. Pero, ¿hacia dónde? y ¿cuánto? son preguntas que debemos definir.

El algoritmo que se siguió lo que hace es, para cada vecino de la celda, calcular primero la diferencia de presión que existe con este vecino.  De esta diferencia de presión solo se pasará cierto porcentaje y a su vez, esta cantidad a pasar antes se mide entre un mínimo y un máximo para mantener una propagación homogenea y que no sucedan cosas como pasar una cantidad negativa de presión hacia la celda vecina.

Como podemos ver en \cite{ca-physical-modeling}, el siguiente algoritmo nos sirve para simular la propagación de presión en un CA.

\begin{mylisting}
\begin{verbatim}
for (neigh = each neighbor celll
{
    if ( neigh->Material->IsInert() ) continue;
    float DPress = cell->Pressure - neigh->Pressure;
    float Flow = cell->Material->Flow * DPress;
    Flow = clamp ( Flow, cell->Pressure / 4.0f, -neigh->Pressure / 4.0f );
    cell->NewPressure -= Flow;
    neigh->NewPressure += Flow;
	
}
\end{verbatim}
\end{mylisting}

donde la función \textit{\textbf{clamp()}} es la que regula la cantidad de flujo a pasar a los vecinos, chequeando que este flujo esté entre un \textit{\textbf{mínimo}} y un \textit{\textbf{máximo}}. Podríamos implementar \textit{\textbf{clamp()}} de la siguiente forma:


\begin{mylisting}
\begin{verbatim}
def clamp(value, max, min):
        '''
        Funcion clamp, devuelve value si value esta entre min y max, devuelve min o max si no.
        '''
        if value<min:
            return min
        if value>max:
            return max
        return value
\end{verbatim}
\end{mylisting}        

La división por 4 que se hace en el algoritmo de cálculo de flujo es debido a que son 4 los vecinos que se están usando, por la vecindad de Von Neumann. De esta forma, nos aseguramos de tener siempre flujo para pasarle a nuestros vecinos. Otros casos de elección de vecinos podrían ser:
\begin{itemize}
\item En 2D, los 8 vecinos de la vecindad de Moore.
\item En 3D, los 6 vecinos que comparten la cara con el cubo central.
\item En 3D, los 6 anteriores más 12 que comparten un borde con el cubo central.
\item En 3D, los 18 anteriores más 8 que comparten una esquina con el cubo central.
\end{itemize} 

Claro que el algoritmo de actualización de presión que vimos se debe correr para cada celda del CA. Se usa una variable para guardar el estado futuro de la presión ya que de no usarse, el cambio de estado del CA no sería síncrono, sino todo lo contrario. Si se actualizara la presión de cada celda cuando se calcula su nueva presión entonces la presión de una celda se propagaría en la dirección que se recorra la matriz del CA. 

Para el ambiente que se desea simular, que se supone homogeneo, necesitamos que la presión se distribuya de la forma más parecida a lo natural posible, similar a la onda que se genera en una superficie de agua por la aplicación de presión en un punto. Este tipo de ondas se propagan a una velocidad característica en todas las direcciónes. Para esto es que necesitamos recorrer una vez el CA para actualizar la presión y guardar este dato en una variable aparte y luego recorrer de nuevo el CA para actualizar los valores de presión, i.e, seguir el siguiente algoritmo.


\begin{mylisting}
\begin{verbatim}
for ( celll in matrix)
{
    cell->Pressure = cell->NewPressure;
}
\end{verbatim}
\end{mylisting}


\subsubsection{• Implementación}
La implementación de este CA fue mediante dos clases principales, la clase \textbf{Matrix()} y la clase \textbf{Celda()}. Como vimos antes, en el \textit{Juego de la Vida}, la clase \textbf{Matrix()} tiene como atributos la matriz en si que interpre el CA, que es un \textit{array de arrays} donde en cada posición hay un objeto del tipo \textbf{Celda()}.

Veamos la clase \textbf{Matrix()} y \textbf{Celda()}:

\begin{mylisting}
\begin{verbatim}
class Matrix():
    """Creo una matriz que sera una lista de listas
    la lista inicial tendra en cada posicion las filas
    de la matriz:
    Ejemplo de matriz 4xn
        [fila1, fila2, fila3, fila4]
    Donde fila_i es una lista de longitud n"""
    
    def __init__(self, rows, cols):
        '''Inicializa una matriz de NxM donde N=rows y M=cols. 
        Todas las celdas se inicializan en 0'''
        self.cols = cols
        self.rows = rows
        
        # Inicializo matriz
        self.matrix = []
        
        for i in range(rows):
            # Creo una fila nuevo
            row = []
            
            for j in range(cols):
                # Lleno la fila con 0 en cada celda
                celda = Celda()
                row.append(celda)
            
            self.matrix.append(row)
            
class Celda():
    '''Define la clase que se usa como celda de una matriz.'''
    def __init__(self, pressure=0, new_pres=0):
        '''Inicializa todos los valores con pressure y los new con new_pressure.'''
        self.pressure = pressure
        self.new_pressure = new_pres
\end{verbatim}
\end{mylisting}

estos son solo los métodos \textit{\textbf{\_\_init\_\_()}} de las clases, i.e, el método que se ejecuta al crear un objeto de esta clase.

Pero como vimos antes, necesitamos alguna forma de actualización de la matriz. Esto es, cómo el CA va a cambiar del estado actual al estado de la generación siguiente. Para esto la clase \textbf{Matrix()} tiene un método que aplica la regla de propagación de presión que vimos anteriormente. El método se llama \textbf{rules()} y se implemntó como sigue:

\begin{mylisting}
\begin{verbatim}
def rules(self):
        '''
        Recorro la matriz. Para cada vecino de la celda:
            1) Obtengo la diferencia de presion 
            2) Uso la funcion clamp() para ajustar el valor a pasar
            3) Transfiero el valor a la celda vecina (a new_pressure)
            4) Resto lo que transferi a la celda que estoy visitando
        '''
        flow = 0.15
        
        for i in range(1, self.rows+1):
            for j in range(1, self.cols+1):
                
                # Obtengo la celda y la marco visitada
                celda = self.get_cell(i,j)
                
                # Obtengo los vecinos de neumann (4 vecinos)
                vecinos = self.vecinos_neumann(i,j)
                
                # Actualizo puntos cardinales
                for punto, vecino in vecinos.items():
                    
                    # Obtengo la diferencia de presion
                    dpres = celda.get_pressure() - vecino.get_pressure()
                    
                    # Ajusto el valor a transferir
                    valor = clamp (flow*dpres, celda.get_pressure()/4, -vecino.get_pressure()/4)
                    
                    # Transfiero el valor al vecino
                    vecino.update_new_pressure( valor)
                    
                    # Resto lo que transferi
                    celda.update_new_pressure(-valor)
                    
        return 
\end{verbatim}
\end{mylisting}

donde \textbf{\textit{flow}} es una constante que define el grado de propagación del medio. Claramente un valor muy chico hará que el flujo transmitido de una celda a sus vecinas sea muy poco, haciendo que la propagación sea más lenta. Por lo tanto, esto podemos adaptarlo según el medio que necesitemos simular.

Luego de llamar a este método, será necesario actualizar los valores de la matriz. Para esto llamamos al método \textbf{\textit{update\_matrix()}} que es tan simple como sigue.

\begin{mylisting}
\begin{verbatim}
def update_matrix(self):
        
        for i in range(1, self.rows+1):
            for j in range(1, self.cols+1):
                self.get_cell(i,j).update()
                
        return 
\end{verbatim}
\end{mylisting}

donde vemos que se llama al método \textit{\textbf{update()}} de la clase celda para cada celda de la matriz. Veamos el método \textit{\textbf{update()}}.

\begin{mylisting}
\begin{verbatim}
def update(self):
        '''Actualiza pressure con el valor de new_pressure.'''
        self.pressure = self.new_pressure
\end{verbatim}
\end{mylisting}




\subsubsection{• Morse+Visión+CA}
\subsubsection{• Observaciones}


\newpage
%\section{• Verificación}
%\subsection{• Reproducción paper Potencial de Morse }
%\subsection{• Verificación VisiLibity}
%\subsection{• Verificación Conways}
%\subsection{• Verificación CA para Presión}

\newpage
\section{• Conclusiones}

\newpage
\section{• Estado del Arte}
Hoy en día \textit{Swarm Intelligence(SI)} es un muy amplio campo de investigación. Las áreas donde se lo puede aplicar son numerosas debido a su robustes, su escalabilidad, su poder de reconfiguración, su tolerancia a fallas, su posiblilidad de administrar tareas en forma paralela. Por todas esas características y más es que la \textit{Inteligencia de Ganado (Swarm Intelligence)} se puede aplicar, entre otras, en las siguiente áreas:
\begin{itemize}
\item Simulaciones de la naturaleza
\item Simulaciones de conductas sociales
\item Transportación
\item Búsqueda y Rescate
\item Detección de minas
\item Vigilancia y monitoreo
\item Servicios médicos
\item Aplicaciones militares
\item Juegos
\item Evacuaciones de gente
\item Analizar performance de Autopistas
%\item etc..
\end{itemize}

Sin embargo, hay dos áreas que claramente han dominado el campo de estudio. Las áreas son \textit{Optimización de Colonia de Hormigas}, del inglés \textit{Ant Colony Optimization (ACO)} y \textit{Optimización Combinatoria}, más conocida como \textit{Particle Swarm Optimization (PSO)}, y son algoritmos de optimización basados en el estudio del comportamiento de rebaños en la naturaleza. 

\textit{Ant Colony Optimization} es un algoritmo probabilístico que se basa en tratar de resolver problemas computacionales que se puedan reducir al comportamiento que tienen las hormigas para encontrar caminos óptimos desde su colonia hasta la comida. Un ejemplo de su aplicación es en el \textit{problema del viajante (Traveling Salesman Problem)}\cite{traveling-salesman-problem}, donde se ha usado de forma positiva \cite{salesman-problem}. Este problema está clasificado técnicamente como de solución en un tiempo no polinomial (NP-Hard). Un problema se considera NP-Hard cuando se demuestra que cualquier algoritmo de solución tiene un tiempo de ejecución que aumenta, en el peor de los casos, exponencialmente con el tamaño del problema.


Por otro lado, el algoritmo de \textit{Particle Swarm Optimization (PSO)}\cite{pso-def}\cite{pso-def2} es un método de optimización numérica que se basa en mantener soluciones o candidatos posibles, llamados partículas y mover éstas partículas en el espacio de búsqueda de la solución óptima siguiendo simples fórmulas para este movimiento. El comportamiento de las partículas se guía en base a la mejor solución encontrada en el espacio de búsqueda, que dicha solución se actualiza constantemente a medida que las partículas encuentran nuevas \textit{mejores soluciones}. 

Un ejemplo de aplicación de el algoritmo PSO es en el problema \textit{Secuenciamiento de Tareas} (Flowshop), que es un problema clásico de la programación de trabajos. La solución del modelo matemático consiste en encontrar una secuencia de tareas que emplee un tiempo mínimo de
procesamiento. Este problema también se considera NP-Hard, como el problema de \textit{Traveling Salesman Problem}.

Este último algoritmo (\textit{PSO}), atrajo la mayor de las atenciones en este último tiempo. La mayoría de los trabajos de investigación relacionadas a este algoritmo se basan en tratar de introducir variantes del mismo \cite{pso-paper1}\cite{pso-paper2}\cite{pso-paper3}\cite{pso-paper4}\cite{pso-paper5}\cite{pso-paper6}.

Otra de las aplicaciones de \textit{Swarm Intelligence} es en situaciones donde el problema se puede dividir en varias \textit{tareas paralelas} que se pueden resolver más eficientemente por un grupo independientes de agentes de las mismas características. Por otro lado, hay problemas donde se necesita agrupar a todos los agentes como una unidad y que trabajen de forma colectiva. Un ejemplo de esto son los sistemas multi-robots donde los robots se conectan fisicamente para alcanzar una tarea determinada. Podemos ver esto en \cite{multi-robots1}\cite{multi-robots2}\cite{multi-robots3}.

También se puede aplicar \textit{Swarm Intelligence} al campo de la exploración. Pensemos un instante en las misiones de la NASA a Marte como \textit{"Spirit and Opportunity"} donde se envió un vehículo explorador. Una mirada distinta sería enviar un grupo grande de vehículos independientes más pequeños y con menos inteligencia que se dediquen a explorar, siguiendo un algoritmo de exploración basado en \textit{Swarm Intelligence}. En el área de exploración podemos ver papers como \cite{exploration-bots1}\cite{exploration-bots2}.




\newpage
\begin{thebibliography}{20}
  \bibitem{nature}Iain D. Couzin, Jens Krause, Nigel R. Franks \& Simon A. Levin,``Effective leadership and decision-making in animal groups on the move'', Nature  www.nature.com/nature, 3 Febrero 2005.
  \bibitem{cooperativ-control}Cooperative Control of Distributed Multi-agent System - edited by Jeff S. Shamma - 2007 - John Wiley \& Sons, Ltd.
  \bibitem{traveling-salesman-problem}\url{http://en.wikipedia.org/wiki/Travelling_salesman_problem}
  \bibitem{salesman-problem}M. Dorigo et L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, volume 1, numéro 1, pages 53-66, 1997.
  \bibitem{pso-def}Kennedy, J.; Eberhart, R. (1995). "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks. IV. pp. 1942-1948.
  \bibitem{pso-def2}\url{http://www.engr.iupui.edu/~shi/Coference/psopap4.html}
  \bibitem{pso-paper1}Chen, H., Zhu, Y., and Hu, K. 2010. Discrete and continuous optimization based on multi-swarm coevolution. Natural Computing: an international journal 9, 3 (Sep. 2010), 659-682. DOI= \url{http://dx.doi.org/10.1007/s11047-009-9174-4}
  \bibitem{pso-paper2}Schoeman, I. L. and Engelbrecht, A. P. 2010. A novel particle swarm niching technique based on extensive vector operations. Natural Computing: an international journal 9, 3 (Sep. 2010), 683-701. DOI=\url{http://dx.doi.org/10.1007/s11047-009-9170-8}
  \bibitem{pso-paper3}Wang, H., Yang, S., Ip, W. H., and Wang, D. 2010. A particle swarm optimization based memetic algorithm for dynamic optimization problems. Natural Computing: an international journal 9, 3 (Sep. 2010), 703-725. DOI=\url{http://dx.doi.org/10.1007/s11047-009-9176-2}
  \bibitem{pso-paper4}Rashedi, E., Nezamabadi-Pour, H., and Saryazdi, S. 2010. BGSA: binary gravitational search algorithm. Natural Computing: an international journal 9, 3 (Sep. 2010), 727-745. DOI= \url{http://dx.doi.org/10.1007/s11047-009-9175-3}
  \bibitem{pso-paper5}Abido, M. A. 2010. Multiobjective particle swarm optimization with nondominated local and global sets. Natural Computing: an international journal 9, 3 (Sep. 2010), 747-766. DOI= \url{http://dx.doi.org/10.1007/s11047-009-9171-7}
  \bibitem{pso-paper6}Ahmadi, A., Karray, F., and Kamel, M. S. 2010. Flocking based approach for data clustering. Natural Computing: an international journal 9, 3 (Sep. 2010), 767-791. DOI= \url{http://dx.doi.org/10.1007/s11047-009-9173-5}
	 
  \bibitem{multi-robots1}Tuci, E., Groß, R., Trianni, V., Mondada, F., Bonani, M., and Dorigo, M. 2006. Cooperation through self-assembly in multi-robot systems. ACM Trans. Auton. Adapt. Syst. 1, 2 (Dec. 2006), 115-150. DOI=\url{http://doi.acm.org/10.1145/1186778.1186779}
  \bibitem{multi-robots2}\url{http://mobots.epfl.ch/self-assembling-robots.html}
  
  \bibitem{multi-robots3}Shervin Nouyan, Marco Dorigo. 2006. "Chain Based Path Formation in Swarms of Robots"
  
  \bibitem{exploration-bots1} Nikolaus Correll, Kjerstin Easton, Alcherio Martinoli, and Joel Burdick. Collaborators: Jonathan Witt, Edmond Wong (NASA Glenn Center). "Distributed Exploration and Coverage"

  \bibitem{exploration-bots2}Weihua Sheng, Qingyan Yang, Jindong Tan, Ning Xi, Distributed multi-robot coordination in area exploration, Robotics and Autonomous Systems, Volume 54, Issue 12, 31 December 2006, Pages 945-955, ISSN 0921-8890, DOI: 10.1016/j.robot.2006.06.003.
(\url{http://www.sciencedirect.com/science/article/B6V16-4KNKBYG-1/2/5eae9bc1ff42374b0c34bb1d88c2a51c})
Keywords: Multi-robot coordination; Exploration
  
  \bibitem{sof-vs-hard-core}Comparison of Hard-Core and Soft-Core Potentials for Modelling Flocking in Free Space
   \bibitem{morse1}S. Camazine \textit{et al.}, \textit{Self Organization in Biological System} (Princeton University Press, Princeton, 2003); I. Prigogine, \textit{Order Out of Chaos} (Bantam, New York, 1993 )
   \bibitem{morse2}J. K. Parrish and L. Edelstein-Keshet, Science 284, 99 (1999); S.A. Kaufmann, \textit{The Origins of Order: Self-Organization and Selection in Evolution} (Oxford University Press, New York, 1993)
  \bibitem{L-J-1}\url{http://www.fisica.uniud.it/~ercolessi/md/md/node15.html}
  \bibitem{L-J-2}\url{http://polymer.bu.edu/Wasser/robert/work/node8.html}
  \bibitem{van-der-waals1}\url{http://web.njit.edu/all_topics/Prog_Lang_Docs/html/autodock/AD3.a.0UserGuide.html}
   \bibitem{28}J. Toner, Y. Tu, Long-range order in a two-dimensional dynamical xy model: How birds fly together, Phys. Rev. Lett., 75 (1995), pp. 43264329.
   \bibitem{29}C.M. Topaz and A.L. Bertozzi, Swarming patterns in a two-dimensional kinematic model for biological groups, SIAM J. Appl. Math., 65 (2004), pp. 152–174.
   \bibitem{30}C.M. Topaz, A.L. Bertozzi, and M.A. Lewis, A nonlocal continuum model for biological aggregation, Bulletin of Mathematical Biology, 68 (2006), pp. 1601-1623.
  \bibitem{phys-flock}T. Vicsek, A. Czir k, E. Ben-Jacob, I. Cohen and O. Shochet, Phys. Rev. Lett. 75, 1226 (1995).
  \bibitem{self-propelled-particle}M.R.D’Orsogna, Y.-L. Chuang, A. L. Bertozzi, L. Chayes, \textit{Self-propelled particles with soft-core interactions: patterns, stability, and collapse,} Phys. Rev. Lett., 96 (2006), pp. 104302- 1/4.
  \bibitem{verlet}\url{http://en.wikipedia.org/wiki/Verlet_integration}
  \bibitem{visiLibity}K. J. Obermeyer and Contributors,The {VisiLibity} library, \url{http://www.VisiLibity.org}, 2008, R-1, A C++ library for floating-point visibility computations
  \bibitem{ca-modeling}Cellular Automata for Physical Modeling. Tom Forsyth, Mucky Foot Productions, Ltd.
  \bibitem{ca-spreadsheet}Simple Cellular Automata on a Spreadsheet, Chris Hand, Post-Doctoral Researcher, Kingston University.
  \bibitem{paul-collahan-math}What is the Game of Life, Paul Callahan, \url{http://www.math.com/students/wonders/life/life.html}.
  \bibitem{paul-conway-turing}A Turing Machine in Conway's Game of Life, extendable to a Universal Turing Machine. Paul Rendell, 2000. \url{http://rendell-attic.org/gol/tm.htm}
  \bibitem{ca-physical-modeling}Cellular Automata for Physical Modeling, Tom Forsyth, Mucky Foot Productions, Ltd.
  \bibitem{verlet_velocity}L. Verlet, Phys. Rev. 159, 98 (1967); Phys. Rev. 165, 201 (1967).
\end{thebibliography}
\end{document}
